ACM基础模板（宏定义、快读快写、快速幂、gcd、组合数与Lucas定理）

//万能头文件
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

#define FAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define X first
#define Y second
typedef long long LL;
typedef unsigned long long ULL;
typedef pair PII;
const int INF = 0x3f3f3f3f;//无穷大
const int MOD = 1e9 + 7;//取余

//快读
inline int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') if (c == '-') { f = -1; c = getchar(); }
    while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
    return x * f;
}

//快写
inline void write(int x)
{
    if (x < 0) { putchar('-'); x = -x; }
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

//最大公约数
int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}

//最小公倍数
int lcm(int a, int b)
{
    return a * b / gcd(a, b);
}

//扩展欧几里得
int exgcd(int a, int b, int &x, int &y)
{
    if (b == 0)
    {
        x = 1; y = 0;
        return a;
    }
    int ans = exgcd(b, a % b, x, y);
    int temp = x;
    x = y;
    y = temp - a / b * y;
    return ans;
}

//快速幂(a ^ b % p)
LL quickMi(LL a, LL b, LL p)
{
    LL res = 1;
    while (b)
    {
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res % p;
}

//快速乘(a * b % p)
LL quickMul(LL a, LL b, LL p)
{
    LL res = 0;
    while (b)
    {
        if (b & 1) res = (res + a) % p;
        a = a * 2 % p;
        b >>= 1;
    }
    return res;
}

//求组合数
LL C(LL a, LL b, LL p)
{
    LL res = 1;
    for (int i = 1, j = a; i <= b; i++, j--)
        res = res * j % p * quickMi(i, p - 2, p) % p;
    return res;
}

//卢卡斯定理
LL lucas(LL a, LL b, LL p)
{
    if (a < p && b < p) return C(a, b, p);
    return C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;
}

int main()
{
    FAST

    return 0;
}
ACM基础模板（宏定义、快读快写、快速幂、gcd、组合数与Lucas定理）

C/C++/C#相关栏目本月热门文章
