解题思路

求组合数值（mod p） 可以将组合数分解成质数，（先分子分解，后分母分解，然后每个质数的个数差），然后再求组合数（mod p）

应用到 线性筛、求一个阶乘含质数个数的公式、高精度乘法

题解

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 5010;

int primes[N], cnt;
bool st[N];
int sum[N];

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++)
    {
        if(!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}
int get(int n, int p)
{
    int res = 0;
    while(n)
    {
        res += n / p;
        n /= p;
    }
    return res;
}
vector<int> mul(vector<int> &A, int b)
{
    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size() || t ; i ++ )
    {
        if (i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }
    while (C.back() == 0 && C.size() > 1) C.pop_back();

    return C;
}


int main()
{
    int a, b;
    cin >> a >> b;

    get_primes(a);

    for (int i = 0; i < cnt; i ++ )
    {
        int p = primes[i];
        sum[i] = get(a, p) - get(b, p) - get(a - b, p);
    }

    vector<int> res;
    res.push_back(1);

    for (int i = 0; i < cnt; i ++ )
        for (int j = 0; j < sum[i]; j ++ )
            res = mul(res, primes[i]);

    for (int i = res.size() - 1; i >= 0; i -- ) printf("%d", res[i]);
    puts("");

    return 0;
}

题解

#include <iostream>

using namespace std;

int main()
{
    double x;
    cin >> x;
    double l = -100, r = 100;
    while (r - l > 1e-8)
    {
        double mid = (l + r) / 2;
        if (mid * mid * mid > x) r = mid;
        else l = mid;
    }
    printf("%lf", l);
    return  0;
}

二分模板

int q[N];
int l = 0, r = n - 1;
        while(l < r)
        {
            int mid = l + r >> 1;
            if (q[mid] >= x) r = mid;
            else l = mid + 1;
        }

int q[N];
int l = 0, r = n - 1;

            while (l < r)
            {
                int mid = l + r + 1 >> 1;
                if (q[mid] <= x) l = mid;
                else r = mid - 1;
            }

题解

#include <iostream>

using namespace std;

const int N = 100010;
int n;
int q[N];


int main()
{
    int m;
    cin >> n >> m;
    for (int i = 0; i < n; i ++ )
        cin >> q[i];
    while(m -- )
    {
        int x;
        cin >> x;
        int l = 0, r = n - 1;
        while(l < r)
        {
            int mid = l + r >> 1;
            if (q[mid] >= x) r = mid;
            else l = mid + 1;
        }
        if (q[l] != x) cout<<"-1 -1\n";
        else
        {
            cout << l << " ";
            l = 0, r = n - 1;

            while (l < r)
            {
                int mid = l + r + 1 >> 1;
                if (q[mid] <= x) l = mid;
                else r = mid - 1;
            }
            cout << l << endl;
        }
    }

    return 0;
}

卡特兰数

解题思路

题解

int qmi(int a, int k)
{
    int res = 1;
    while(k)
    {
        if(k & 1) res = (LL)res * a % p;
        k >>= 1;
        a = (LL)a * a % p;
    }

    return res;
}



int C(int a, int b)
{
    int res = 1;
    for(int i = 1, j = a; i <= b; i ++, j -- )
    {
        res = (LL)res * j % p;
        res = (LL)res * qmi(i, p - 2)% p;
    }
    return res;
}


int lucas(LL a, LL b)
{
    if (a < p && b < p) return C(a, b);
    return (LL)C(a % p, b % p) * lucas(a / p, b / p) % p;
}

解题思路

模板

int p;
int qmi(int a, int k)
{
    int res = 1;
    while(k)
    {
        if(k & 1) res = (LL)res * a % p;
        k >>= 1;
        a = (LL)a * a % p;
    }

    return res;
}



int C(int a, int b)
{
    int res = 1;
    for(int i = 1, j = a; i <= b; i ++, j -- )
    {
        res = (LL)res * j % p;
        res = (LL)res * qmi(i, p - 2)% p;
    }
    return res;
}


int lucas(LL a, LL b)
{
    if (a < p && b < p) return C(a, b);
    return (LL)C(a % p, b % p) * lucas(a / p, b / p) % p;
}

题解

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

int p;

int qmi(int a, int k)
{
    int res = 1;
    while(k)
    {
        if(k & 1) res = (LL)res * a % p;
        k >>= 1;
        a = (LL)a * a % p;
    }

    return res;
}



int C(int a, int b)
{
    int res = 1;
    for(int i = 1, j = a; i <= b; i ++, j -- )
    {
        res = (LL)res * j % p;
        res = (LL)res * qmi(i, p - 2)% p;
    }
    return res;
}


int lucas(LL a, LL b)
{
    if (a < p && b < p) return C(a, b);
    return (LL)C(a % p, b % p) * lucas(a / p, b / p) % p;
}

int main()
{
    int n;
    cin >> n;
    while(n -- )
    {
        LL a, b;
        cin >> a >> b >> p;
        cout << lucas(a, b) << endl; 
    }


    return 0;
}

解题思路

题解

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010, mod = 1e9 + 7;

typedef long long LL;

int fact[N], infact[N];

int qmi(int a, int k, int p)
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = (LL) res * a % p;
        a = (LL) a * a % p;
        k >>= 1;
    }
    return res;
}



int main()
{
    fact[0] = infact[0] = 1;
    for (int i = 1; i < N; i ++)
    {
        fact[i] = (LL)fact[i - 1] * i % mod;
        infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;
    }
    int n;
    cin >> n;
    while(n --)
    {
        int a, b;
        scanf("%d%d",&a, &b);
        printf("%d\n",(LL)fact[a] * infact[b] % mod * infact[a - b] % mod);
    }

    return 0;

}

解题思路

模板

void init()
{
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j <= i; j ++ )
            if(!j) c[i][j] = 1;
            else c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;

}

题解

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 2010, mod = 1e9 + 7;
int c[N][N];

void init()
{
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j <= i; j ++ )
            if(!j) c[i][j] = 1;
            else c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;

}

int main()
{
    init();
    int n;
    cin >> n;
    while (n -- )
    {
        int a, b;
        cin >> a >> b;
        cout << c[a][b] << endl;
    }
    return 0;
}

解题思路

模拟消元过程

题解

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

const int N = 110;
const double eps = 1e-6;
int n;
double a[N][N];

int gauss()
{
    int c, r;// c 为列   r 为行
    for (c = 0, r = 0; c < n; c ++ )// 枚举每一列
    {
        int t = r;//记录当前行
        for (int i = r; i < n; i ++ ) // 寻找绝对值最大值
            if (fabs(a[i][c]) > fabs(a[t][c]))
                t = i;
        if(fabs(a[t][c]) < eps) continue;//此列下面都是0  下一列开始

        for (int i = c; i <= n; i ++ ) swap(a[t][i], a[r][i]); //将最大值列 放入当前行
        for(int i = n; i >= c; i -- ) a[r][i] /= a[r][c];//将当前行t 的c列置为1  从后往前消，否则第一项为1，无法消后项

        for(int i = r + 1; i < n; i ++ )//将下面行的此列消为0
            if (fabs(a[i][c]) > eps)//非零则消
                for(int j = n; j >= c; j --)   
                    a[i][j] -= a[r][j] * a[i][c];

        r ++;
    }//当枚举完c列时，r最大为n
    if (r < n)
    {
        for (int i = r; i < n; i ++)
            if (fabs(a[i][n]) > eps)
                return 2;
        return 1;
    }
    for (int i = n - 1; i >= 0; i -- )
        for(int j = i + 1; j < n; j ++ )
            a[i][n] -= a[i][j] * a[j][n];
    return 0;
}


int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ )
        for(int j = 0; j < n + 1; j ++ )
            cin >> a[i][j];
    int t = gauss();
    if (t == 0) 
    {
        for (int i = 0; i < n; i ++ ) printf("%.2lf\n", a[i][n]);
    }
    else if (t == 1) puts("Infinite group solutions");
    else puts("No solution");

    return 0;
}

题解

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

LL exgcd(LL a, LL b,LL &x, LL &y)
{
    if(!b)
    {
        x = 1, y = 0;
        return a;
    }
    LL d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
int main()
{
    int n;
    cin >> n;

    bool has_answer = true;
    LL a1, m1;

    cin >> a1 >> m1;

    for (int i = 0; i < n; i ++)
    {
        LL a2, m2;
        cin >> a2 >> m2;

        LL k1, k2;
        LL d = exgcd(a1, a2, k1, k2);
        if((m2 - m1) % d)
        {
            has_answer = false;
            break;
        }

        k1 *= (m2 - m1) / d;
        LL t = a2 / d;
        k1 = (k1 % t + t) % t;

        m1 = a1 * k1 + m1;
        a1 = abs(a1 / d * a2);
    }
    if (has_answer)
    {
        cout << (m1 % a1 + a1) % a1 << endl;
    }
    else puts("-1");
    return 0;
}

转化成扩展欧几里得

题解

#include <iostream>
using namespace std;

typedef long long LL;

int exgcd(int a, int b, int &x, int &y)
{
    if(!b)
    {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

int main()
{
    int n;
    cin >> n;
    while(n --)
    {
        int a, b, m;
        int x, y;
        scanf("%d%d%d",&a, &b, &m);
        int d = exgcd(a, m, x, y);
        if (b % d != 0) puts("impossible");
        else printf("%d\n",(LL)b / d * x % m);

    }
    return 0;
}