ACM

数学知识

数学知识

[TOC]

高精度

  1. 加法
string add(const string& A, const string& B)
{
    string C;
    int t = 0;
    for (int i = A.size()-1, j = B.size()-1; i >= 0 || j >= 0 || t > 0; i--, j--)
    {
        if (i >= 0) t += (A[i] - '0');
        if (j >= 0) t += (B[j] - '0');
        C += ((t % 10) + '0');
        t /= 10;
    }

    reverse(C.begin(), C.end());
    return C;
}
  1. 减法
// 给定两个正整数

#include <iostream>
#include <vector>

using namespace std;

bool cmp(vector<int>& A, vector<int> &B)
{
    if(A.size() != B.size()) return A.size() > B.size();  //直接ruturn 了就不用else

    for(int i = A.size(); i >= 0; i--)
        if(A[i] != B[i])
            return A[i] > B[i];

    return true;
}

vector <int> sub(vector<int>& A, vector<int> &B)
{
    vector<int> C;
    int t = 0;
    for(int i = 0; i < A.size(); i++)
    {
        t = A[i] - t;
        if(i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10 ); // 合而为1
        if(t < 0)  t = 1;
        else t = 0;

    }

    while(C.size() > 1 && C.back() == 0) C.pop_back();  //去掉前导0

    return C;
}

int main()
{
    string a ,b;
    vector<int> A, B;

    cin >> a >> b ;

    for(int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
    for(int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');

    if (cmp(A,B)) 
    {
        auto C = sub(A, B);
        for(int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
        return 0;
    }
    else
    {
        auto C = sub(B, A);
        printf("-");
        for(int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
        return 0;
    }


}
  1. 高精*低精
#include <iostream>
#include <vector>

using namespace std;

vector <int> mul(vector <int> & A, int b) {
    vector <int> C;

    int t = 0;
    for (int i = 0; i < A.size(); i ++) {
        t += A[i] * b;       // t + A[i] * b = 7218
        C.push_back(t % 10); // 只取个位 8
        t /= 10;             // 721 看作 进位
    }

    while (t) {            // 处理最后剩余的 t
        C.push_back(t % 10);
        t /= 10;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();

    return C;
}

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

    vector <int> A;
    for (int i = a.size() - 1; i >= 0; i --) A.push_back(a[i] - '0');

    auto C = mul(A, b);

    for (int i = C.size() - 1; i >= 0; i --) {
        cout << C[i];
    }

    return 0;
}
  1. 高精*高精
#include <iostream>
#include <vector>

using namespace std;

vector<int> mul(vector<int> &A, vector<int> &B) {
    vector<int> C(A.size() + B.size() + 7, 0); // 初始化为 0，C的size可以大一点

    for (int i = 0; i < A.size(); i++)
        for (int j = 0; j < B.size(); j++)
            C[i + j] += A[i] * B[j];

    int t = 0;
    for (int i = 0; i < C.size(); i++) { // i = C.size() - 1时 t 一定小于 10
        t += C[i];
        C[i] = t % 10;
        t /= 10;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back(); // 必须要去前导 0，因为最高位很可能是 0
    return C;
}

int main() {
    string a, b;
    cin >> a >> b; // a = "1222323", b = "2323423423"

    vector<int> A, B;
    for (int i = a.size() - 1; i >= 0; i--)
        A.push_back(a[i] - '0');
    for (int i = b.size() - 1; i >= 0; i--)
        B.push_back(b[i] - '0');

    auto C = mul(A, B);

    for (int i = C.size() - 1; i >= 0; i--)
        cout << C[i];

    return 0;
}
  1. 高精/低精
#include<bits/stdc++.h>
using namespace std;
vector<int>a,b,c;
int main(){
	string aa;
	cin>>aa;
	int b;
	cin>>b;
	for(int i=aa.size()-1;i>=0;i--){
		a.push_back(aa[i]-'0');
	} 
	int t=0;
	for(int i=aa.size()-1;i>=0;i--){
		t+=a[i];
		c.push_back(t/b);
		t%=b;
		t*=10;
	}
	int i=0;
	while(i<aa.size()-1&&c[i]==0)i++;
	while(i<aa.size()){
		printf("%d",c[i]);
		i++;
	}
	printf("\n%d",t/10);
	return 0;
}
  1. 高精/高精
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

bool cmp(vector<int> &A, vector<int> &B){
    if(A.size()!=B.size()) return A.size()>B.size();
    for(int i=A.size()-1;i>=0;i--){
        if(A[i]!=B[i]) return A[i]>B[i]; 
    }
    return true;
}

vector<int> sub(vector<int> &A,vector<int> &B){
    vector<int> C;
    int t=0;
    for(int i=0;i<A.size()||t;i++){
        t = A[i] - t;
        if(i<B.size()) t -= B[i];
        C.push_back((t+10)%10);
        if(t<0) t = 1;
        else t = 0;
    }
    while(C.size()>1&&C.back()==0) C.pop_back();
    return C;
}

vector<int> div(vector<int> &A, vector<int> &B, vector<int> &r){
    vector<int> C;
    int j = B.size();
    r.assign(A.end()-j,A.end());
    while(j<=A.size()){
        int k=0;
        while(cmp(r,B)){
            vector<int> s = sub(r,B);
            r.clear();
            r.assign(s.begin(),s.end());
            k++;
        }
        C.push_back(k);
        if(j<A.size()) r.insert(r.begin(),A[A.size()-j-1]);
        if(r.size()>1&&r.back()==0) r.pop_back();
        j++;
    }
    reverse(C.begin(),C.end());
    while(C.size()>1&&C.back()==0) C.pop_back();
    return C;
}

int main(){
    string a,b;
    cin>>a>>b;
    vector<int> A,B,r;
    for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
    for(int i=b.size()-1;i>=0;i--) B.push_back(b[i]-'0');

    auto C = div(A,B,r);
    for(int i=C.size()-1;i>=0;i--) printf("%d",C[i]);
    printf("\n");
    for(int i=r.size()-1;i>=0;i--) printf("%d",r[i]);
    return 0;
}

线性筛质数+求欧拉函数

const int N=1000010;
int p[N],cnt,phi[N];
bool st[N];
/*st数组可以换成：
int mind[N];
mind[i]表示i的最小素数
*/

int main(){
    int n;
    cin>>n;
    phi[1]=1;
    for(int i=2;i<=n;i++){
    	if(!st[i]){
    		p[cnt++]=i;
    		phi[i]=i-1;
            //mind[i]=i;
		}
		for(int j=0;p[j]<=n/i;j++){
            st[i*p[j]]=1;
            //mind[i]=p[j];
			if(i%p[j]==0){
				phi[i*p[j]]=phi[i]*p[j];
				break;
			}
			else{
				phi[i*p[j]]=phi[i]*(p[j]-1);
			}
		}
	}
	long long ans=0;
	for(int i=1;i<=n;i++){
		ans+=phi[i];
	}
	cout<<ans;
	return 0;
}

快速幂+快速幂求逆元+龟速乘

long long f(long long a,long long b,long long p){
    long long ans=1;
    while(b>0){
        if(b&1){
            ans=ans*a%p;
        }
        b>>=1;
    	a=a*a%p;
    }
    return ans;
}
//b存在乘法逆元的充要条件是b与模数m互质
if(a%p){
    long long ans=f(a,p);
    printf("%lld\n",ans);
}
else{
    printf("impossible\n");
}

//龟速乘
LL qmul(LL a, LL b, LL c) {
    LL res = 0;
    while (b) {
        if (b & 1) res = (res + a) % c;
        a = (a + a) % c;
        b >>= 1;
    }
    return res;
}

扩展欧几里得

  1. 基本形式
#include<iostream>
using namespace std;
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;
	int a,b,x,y;
	while(n--){
		cin>>a>>b;
		exgcd(a,b,x,y);
		cout<<x<<" "<<y<<endl;
	}
	return 0;
}

//Stein算法在求gcd中素数很大的数字有优势
int KGCD(int a,int b)
{
	if(a == 0)	return b;
	if(b == 0)	return a;
	if(~a & 1)
	{
		if(b & 1)	return KGCD(a>>1, b);
		else	return KGCD(a>>1, b>>1) << 1;
	}
	if(~b & 1)	return KGCD(a, b>>1);
	if(a > b)	return KGCD((a-b)>>1, b);
	return	KGCD((b-a)>>1, a);
}

  1. 应用

    1. 线性方程通解、最小正整数解

      ax + by = c 已知a,b,c,求x最小非负整数
int d = exgcd(a, b, x0, y0);
c%d==0有解
特解：x1=x0*c/d,y1=y0*c/d
结合ax+by=0的齐次解,
通解：x=x1+k*(b/d),y=y1-k*a/d
另t=b/d,最小非负整数解x=(x1%t+t)%t

    2. 一次同余方程、求逆元

      ax=b(mod m)
等价于ax+my=b;
b=1且a与m互质时x即为a的逆元，要求最小的可参见上文

同余式的性质

  1. $ax_1 \equiv ax_2(mod m)$，则$x_1 \equiv x_2 (mod {m\over (a,m)})$
  2. $a \equiv b (mod m), d=(a,b),a=a_1 d,b=b_1 d,(d,m)=1,则a_1 \equiv b_1 (mod m)$
  3. $a \equiv b (mod m),则ak \equiv bk (mod mk)$
  4. $a \equiv b (mod m),d|(a,b,m),则a_1 \equiv b_1(mod m_1)$
  5. $ a\equiv b(mod m),d|m,则a \equiv b(mod d)$
  6. $ a\equiv b(mod m),k|a,k|m,则k|b$
  7. $ a\equiv b(mod m) 则（a,m)=(b,m)$

扩展中国剩余定理+最小非负整数解

$x=m_i(mod a_i),n<25,m_i<a_i$

扩展：$m_i$ 不能保证两两互质

//不存在则输出-1
#include <cstdio>
#include <iostream>
using namespace std;
typedef long long LL;
int n;
LL exgcd(LL a, LL b, LL &x, LL &y){
    if(b == 0){
        x = 1, y = 0;
        return a;
    }

    LL d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
LL inline mod(LL a, LL b){
    return ((a % b) + b) % b;
}
int main(){
    scanf("%d", &n);
    LL a1, m1;
    scanf("%lld%lld", &a1, &m1);
    for(int i = 1; i < n; i++){
        LL a2, m2, k1, k2;
        scanf("%lld%lld", &a2, &m2);
        LL d = exgcd(a1, -a2, k1, k2);
        if((m2 - m1) % d){ puts("-1"); return 0; }
        k1 = mod(k1 * (m2 - m1) / d, abs(a2 / d));
        m1 = k1 * a1 + m1;
        a1 = abs(a1 / d * a2);
    }
    printf("%lld\n", m1);
    return 0;
}

高斯消元

  1. 解n元线性方程组

$a_11 x_1 +a_12x_2+…+a_{1n} x_n = b_1,$

…

$a_{m1} x_1 +a_{m2}x_2+…+a_{mn} x_n = b_m,$

枚举每一列c，

找到当前列绝对值最大的一行

用初等行变换(2) 把这一行换到最上面（未确定阶梯型的行，并不是第一行）

用初等行变换(1) 将该行的第一个数变成 1（其余所有的数字依次跟着变化）

用初等行变换(3) 将下面所有行的当且列的值变成 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 代表 列 col ， r 代表 行 row
    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;
        for (int i = c; i < n + 1; i ++ ) swap(a[t][i], a[r][i]);
        for (int i = n; i >= c; i -- ) a[r][i] /= a[r][c];
        for (int i = r + 1; i < n; i ++ )
            if (fabs(a[i][c]) > eps)
                for (int j = n; j >= c; j -- )
                    a[i][j] -= a[r][j] * a[i][c];
    
        r ++ ;
    }
    
    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[j][n] * a[i][j];
    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;
}

  1. 解异或线性方程组

    形式：把加号换成^，aij都是0或1

    #include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int n;
int a[N][N];//a[i][j]=0或1
int gauss()
{
    int c,r;
    for(c=0,r=0;c<n;c++)
    {
        // 找主元
        int t=-1;
        for(int i=r;i<n;i++)
            if(a[i][c])
            {
                t=i;
                break;
            }
        if(t==-1) continue;
        // 交换主元行
        for(int j=c;j<=n;j++) swap(a[r][j],a[t][j]);
        // 左下角消
        for(int i=r+1;i<n;i++)
            if(a[i][c])//漏了
                for(int j=n;j>=c;j--)//漏了
                    a[i][j] ^= a[r][j];
        r++;
    }
    // 判断
    if(r<n)
    {
        for(int i=r;i<n;i++)//i=r
            if(a[i][n])
                return 2;
        return 1;
    }
    // 消右上角
    for(int i=n-1;i>=0;i--)
        for(int j=i+1;j<n;j++)
        //如果是0 就不用下面的a[j][j] 来^a[i][j]了
        //如果不是0 才需要用第j行第j列a[j][j]来^第i行第j列a[i][j] 
        //进而进行整行row[i]^row[j] 间接导致 a[i][n]^a[j][n]
            if(a[i][j])
                a[i][n]^=a[j][n];
    return 0;
}

int main()
{
    cin >> n;
    for(int i=0;i<n;i++)
        for(int j=0;j<=n;j++)
            cin >> a[i][j];
    int t = gauss();
    if(t==0)
    {
        for(int i=0;i<n;i++) cout << a[i][n] << endl;
    }
    else if(t==1) puts("Multiple sets of solutions");
    else puts("No solution");
    return 0;
}

求组合数

  1. 基础方法$O(n^2)$

    c(a,b)=c(a-1,b)+c(a-1,b-1)

    #include<bits/stdc++.h>
using namespace std;
const int N=2010,M=1e9+7;
long long c[N][N];
int main(){
    for(int i=0;i<=2000;i++){
    	c[i][0]=1;
	}
	for(int i=0;i<=2000;i++){
		for(int j=1;j<=i;j++){
			c[i][j]=(c[i-1][j-1]+c[i-1][j])%M;
		}
	}
	int n,a,b;
	scanf("%d",&n);
	while(n--){
		scanf("%d%d",&a,&b);
		printf("%lld\n",c[a][b]);
	}
}

  2. a，b较大时$O(a log(mod))$

    n次查询，每次给一组a,b，求C(a,b)mod(1e9+7)

    c(a,b)=a!/(b!(a-b)!)

    #include<iostream>
using namespace std;
const int mod=1e9+7,N=1e5+10;
typedef long long LL;
long long fac[N],infac[N];
int main()
{
    int n;
    fac[0]=infac[0]=1;
    for(int i=1;i<=1e5;i++)
    {
        fac[i]=fac[i-1]*i%mod;
        infac[i]=(LL)infac[i - 1] * quick_pow(i,mod-2,mod)%mod;
    }
    cin>>n;
    while(n--)
    {
        int a,b;
        cin>>a>>b;
        cout<<(LL)fac[a] * infac[b] % mod * infac[a - b] % mod<<endl;
    }
}

  3. 查询的数量少且a,b很大-lucas定理

    n组，每组a,b,p,求c(a,b)modp,其中n<=20,a,b<1e18,p<1e5

    lucas定理：c(a,b)=c(a/p,b/p)*c(a mod p,b mod p) (mod p)

    #include<iostream>
#include<algorithm>

using namespace std;

typedef long long LL;

int C(int a,int b,int p)
{
    if(b>a)return 0;
    int res = 1;
    // a!/(b!(a-b)!) = (a-b+1)*...*a / b! 分子有b项
    for(int i=1,j=a;i<=b;i++,j--)//i<=b而不是<
    {
        res = (LL)res*j%p;
        res = (LL)res*qmi(i,p-2,p)%p;
    }
    return res;
}
int lucas(LL a,LL b,int p)
{
    if(a<p && b<p)return C(a,b,p);
    return (LL)C(a%p,b%p,p)*lucas(a/p,b/p,p)%p;
}

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

矩阵乘法+斐波那契数列

  1. 矩阵乘法
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdlib>

using namespace std;

typedef long long ll;

const int N = 3;

int n, m;
ll A[N][N] =    // 上述矩阵 A
{
    {2, 0, -1},
    {1, 0, 0},
    {0, 1, 0}
};
ll S[N] = {2, 1, 0}; // 上述矩阵 S（转置）

void multi(ll A[], ll B[][N]) // 计算方阵 B 乘向量 A，并将结果储存在 A 中
{
    ll ans[N] = {0};
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j < N; j ++ )
            ans[i] += A[j] * B[i][j] % m;
    for (int i = 0; i < N; i ++ )
        A[i] = ans[i] % m;
}

void multi(ll A[][N], ll B[][N]) // 计算方阵 A * B，并将结果储存在 A 中
{
    ll ans[N][N] = {0};
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j < N; j ++ )
            for (int k = 0; k < N; k ++ )
                ans[i][j] += A[i][k] * B[k][j] % m;
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j < N; j ++ )
            A[i][j] = ans[i][j] % m;
}

int main()
{
    scanf("%d%d", &n, &m);

    while (n)        // 矩阵快速幂
    {
        if (n & 1) multi(S, A);
        multi(A, A);
        n >>= 1;
    }

    printf("%lld", (S[2] % m + m) % m);

    return 0;
}

  1. 斐波那契数列

    f(1)=1,f(2)=1，f(3)=2

    则f1+f2+…+fn=f(n+2)-f(2)=f(n+2)-1

博弈论

若一个游戏满足：

由两名玩家交替行动 在游戏进行的任意时刻，可以执行的合法行动与轮到哪位玩家无关 不能行动的玩家判负 则称该游戏为一个公平组合游戏。

尼姆游戏（NIM）属于公平组合游戏，但常见的棋类游戏，比如围棋就不是公平组合游戏，因为围棋交战双方分别只能落黑子和白子，胜负判定也比较负责，不满足条件2和3。

  1. Nim游戏

给定n堆石子，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作的人视为失败。问如果两人都采用最优策略，先手是否必胜。对所有ai按位异或，不等于0则先手必胜

  1. 台阶-nim游戏

现在，有一个 n级台阶的楼梯，每级台阶上都有若干个石子，其中第 i级台阶上有 ai个石子(i≥1)。

两位玩家轮流操作，每次操作可以从任意一级台阶上拿若干个石子放到下一级台阶中（不能不拿）。

已经拿到地面上的石子不能再拿，最后无法进行操作的人视为失败。如果先手时奇数台阶上的值的异或值为非0，则先手必胜，反之必败

  1. 集合-Nim游戏

给定 n堆石子以及一个由 k个不同正整数构成的数字集合 S。现在有两位玩家轮流操作，每次操作可以从任意一堆石子中拿取石子，每次拿取的石子数量必须包含于集合 S，最后无法进行操作的人视为失败。

​ 1.Mex运算: ​ 设S表示一个非负整数集合.定义mex(S)为求出不属于集合S的最小非负整数运算,即: ​ mes(S)=min{x}; ​ 例如:S={0,1,2,4},那么mes(S)=3;

​ 2.SG函数 ​ 在有向图游戏中,对于每个节点x,设从x出发共有k条有向边,分别到达节点y1,y2,····yk,定义SG(x)的后记节点y1,y2,···· ​ yk的SG函数值构成的集合在执行mex运算的结果,即: ​ SG(x)=mex({SG(y1),SG(y2)····SG(yk)}) ​ 特别地,整个有向图游戏G的SG函数值被定义为有向图游戏起点s的SG函数值,即 SG(G)=SG(s).

​ 3.有向图游戏的和 ​ 设G1，G2,····,Gm是m个有向图游戏.定义有向图游戏G,他的行动规则是任选某个有向图游戏Gi,并在Gi上行动一步.G被称为有向图游 戏G1,G2,·····,Gm的和. ​ 有向图游戏的和的SG函数值等于它包含的各个子游戏SG函数的异或和,即: ​ SG(G)=SG(G1)xorSG(G2)xor···xor SG(Gm)

#include<iostream>
#include<cstring>
#include<algorithm>
#include<set>

using namespace std;

const int N=110,M=10010;
int n,m;
int f[M],s[N];//s存储的是可供选择的集合,f存储的是所有可能出现过的情况的sg值

int sg(int x)
{
    if(f[x]!=-1) return f[x];
    //因为取石子数目的集合是已经确定了的,所以每个数的sg值也都是确定的,如果存储过了,直接返回即可
    set<int> S;
    //set代表的是有序集合(注:因为在函数内部定义,所以下一次递归中的S不与本次相同)
    for(int i=0;i<m;i++)
    {
        int sum=s[i];
        if(x>=sum) S.insert(sg(x-sum));
        //先延伸到终点的sg值后,再从后往前排查出所有数的sg值
    }

    for(int i=0;;i++)
    //循环完之后可以进行选出最小的没有出现的自然数的操作
     if(!S.count(i))
      return f[x]=i;
}

int main()
{
    cin>>m;
    for(int i=0;i<m;i++)
    cin>>s[i];

    cin>>n;
    memset(f,-1,sizeof(f));//初始化f均为-1,方便在sg函数中查看x是否被记录过

    int res=0;
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        res^=sg(x);
        //观察异或值的变化,基本原理与Nim游戏相同
    }

    if(res) printf("Yes");
    else printf("No");

    return 0;
}

  1. 移棋子游戏

    n个结点的有向无环图，共m条边，其中一些结点有棋子，共k个棋子。玩家每一步可将任意一颗棋子沿一条有向边移动到另一个点，无法移动者输掉游戏。询问先手必胜还是先手必败。

int n, m, k;
int h[N], e[M], ne[M], idx;          // 邻接表存图
int sg[N];                           // 存所有被计算过的点的 SG 函数值
int res;

int SG(int u)
{
    if (~sg[u]) return sg[u];        // 如果当前 sg[u] 不是 -1，那么说明该点的 SG 函数值已经被计算过了，直接返回
    set<int> S;                      // 否则要建一个集合 S，存该点能到的所有点的 SG 函数值
    for (int i = h[u]; i; i = ne[i]) // 遍历点 u 能到达的所有点
        S.insert(SG(e[i]));          // 计算该点的 SG 函数值，并放入集合 S
    for (int i = 0; ; i ++ )         // 从 0 开始枚举所有非负整数
        if (!S.count(i))             // 如果该值没有在 S 中出现过
        {
            sg[u] = i;               // 那么将该值记录在 sg[u] 中并返回
            return i;
        }
}

int main()
{
    scanf("%d %d %d", &n, &m, &k);   // 读入题目中 N, M, K
    for (int i = 0; i < m; i ++ )    // 读入 M 条边并建图
    {
        int u, v;
        scanf("%d %d", &u, &v);
        add(u, v);
    }
    memset(sg, -1, sizeof sg);       // 先将 sg 数组中的所有值初始化成 -1，表示没有记录过
    while (k -- )                    // 读入 K 个棋子所在的点
    {
        int u;
        scanf("%d", &u);
        res ^= SG(u);
    }
    if (res) puts("win");            // 如果 res 不为 0，那么输出 win
    else    puts("lose");            // 否则输出 lose
    return 0;
}

其他

卡特兰数

${c(2n,n)}\over{n+1}$

$C(n+1)=C(0)C(n)+C(1)C(n-1)+…+C(n)C(0)$

扩展：向右一共走n格，向上一共m格，n>=m，过程中向右的数量不小于向上的数量$c(m+n,n)-c(m+n,m-1)$

n + 1 个叶子节点能够构成多少种形状不同的（国际）满二叉树

（国际）满二叉树定义：如果一棵二叉树的结点要么是叶子结点，要么它有两个子结点，这样的树就是满二叉树。

使用深度优先搜索这个满二叉树，向左扩展时标记为 +1，向右扩展时标记为 -1。

由于每个非叶子节点都有两个左右子节点，所有它必然会先向左扩展，再向右扩展。总体下来，左右扩展将会形成匹配，即变成进出栈的

题型。n + 1个叶子结点会有 2n 次扩展，构成${c(2n,n)}\over{n+1}$种形状不同的满二叉树。

错排问题

全错排的个数：$D_n=(n-1)(D_{n-1}+D_{n-2}),n\geqslant3$，其中易知$D_0=1$，$D_1=0$，$D_2=1$

全错排通项公式：$D_n=n!\sum\limits_{i=0}^n \dfrac{(-1)^i}{i!}$

部分错排，即n个信封有k个装对的个数：$F(n,k)=C_n^kD_{n-k}=\dfrac{n!}{k!}\sum\limits_{i=0}^{n-k} \dfrac{(-1)^i}{i!}$

分治法求约数之和

//求p^0+p^1+...+p^(k-1)
int sum(int p, int k) {
    if(k == 1) return 1;  //边界
    if(k % 2 == 0) {  
        return (LL)(qmid(p, k / 2) + 1) * sum(p, k / 2) % mod;
    }
    return (qmid(p, k - 1) + sum(p, k - 1)) % mod;
}

塞瓦维斯特定理

已知a,b为大于1的正整数，$(a,b)=1$,则使不定方程$ax+by=C$无负整数解的最大整数$C=ab-a-b$

纸牌分发问题

有 n个小朋友坐成一排/圈，每人有 a[i]个糖果。每人只能给左右两人传递糖果，每人每次传递一个糖果代价为 1。求使所有人获得均等糖果的最小代价。

  1. 非环形
//每一堆牌只会受相邻的牌影响，因此从左开始，每一堆牌为了达到平均值，就得向右边的牌索取（或给予），并且步数+1
//于是这堆达到平均值的牌就可以当做已经不存在，继续处理接下来的牌
#include <iostream>

using namespace std;

const int N = 110;

int a[N];
int n , total;
int ans;

int main()
{
    cin >> n;

    for(int i = 1 ; i <= n ; i++) cin >> a[i] , total += a[i];

    int avg = total / n;

    for(int i = 1 ; i <= n ; i++)
        if(a[i] != avg) a[i + 1] += a[i] - avg , ans++;

    cout << ans << endl;
    return 0;
}

  1. 环形

    //数组a,长度为n
ll get(int *a, int n) {
    ll ans = 0;
    for (int i = 1; i <= n; ++i) ans += a[i];
    ans /= n;
    for (int i = 1; i <= n; ++i) a[i] -= ans;
    c[1] = 0;
    for (int i = 2; i <= n; ++i) c[i] = c[i - 1] + a[i];
    sort(c + 1, c + n + 1);
    int mid = c[n / 2 + 1];
    ll sum = 0;
    for (int i = 1; i <= n; ++i) sum += abs(c[i] - mid);
    return sum;
}

容斥原理

状态压缩+计算1的数量即可实现

//a1+a2+...+an=m,0<=ai<=Ai给出n,m,Ai,求方案数
//O(n*2^n)
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
typedef long long ll;
const int N=25;
ll n,m;
int res;
ll a[N];
int down=1;
int ksm(int a,int b) {
    int res=1;
    while(b) {
        if(b&1) res=1ll*res*a%mod;
        a=1ll*a*a%mod;
        b>>=1;
    }
    return res;
}
int C(ll a,ll b) {
    if(a<b) return 0;
    int up=1;
    for(ll i=a; i>a-b; --i) up=i%mod*up%mod;
    return 1ll*up*down%mod;
}
int main() {
    scanf("%lld%lld",&n,&m);
    for(int i=0; i<n; ++i) scanf("%lld",&a[i]);
    for(int i=1; i<=n-1; ++i) down=1ll*i*down%mod;
    down=ksm(down,mod-2);
    for(int i=0; i<(1<<n); ++i) {
        ll d=m+n-1,up=n-1;
        int sign=1;
        for(int j=0; j<n; ++j) {
            if((i>>j)&1) {
                sign*=-1;
                d-=a[j]+1;
            }
        }
        res=(res+C(d,up)*sign)%mod;
    }
    printf("%d\n",(res+mod)%mod);
    return 0;
}

斯特林数

  1. 第一类Stirling数

    分为有符号和无符号两种，无符号：

    表示将 n 个不同元素构成m个圆排列的数目。

    （1）如果n个元素构成了m-1个圆排列，那么第n+1个元素独自构成一个圆排列。方案数：$s(n,m-1)$

    （2）如果n个元素构成了m个圆排列，将第n+1个元素插入到任意元素的左边。方案数：$s(n,m)$

    综合两种情况得：$s(n+1,m)=s(n,m-1)-n*s(n,m)$

    性质

    1. $s(0,0)=1$
    2. $s(n,0)=0$
    3. $s(n,n)=1$
    4. $s(n,1)=(n-1)!$
    5. $s(n,n-1)=C(n,2)$
    6. $s(n,2)=(n-1)!\sum\limits_{i}^{n-1} {1 \over i}$
    7. $s(n,n-2)=2C(n,3)+3C(n,4)$
    8. $\sum\limits_{k=0}^{n}s(n,k)=n!$

    有符号Stirling性质类似：

    1. S(n,m)=(-1)^{n+m}s(n,m) 1. $\sum\limits_{k=0}^{n}S(n,k)=0^n$ 1. 注意$0^0=1$

    解锁仓库问题。

    问题说明如下：有n个仓库，每个仓库有两把钥匙，共2n把钥匙。同时又有n位官员。问如何放置钥匙使得所有官员都能够打开所有仓库？（只考虑钥匙怎么放到仓库中，而不考虑官员拿哪把钥匙。）那如果官员分成m个不同的部，部中的官员数量和管理的仓库数量一致。那么有多少方案使得，同部的所有官员可以打开所有本部管理的仓库，而无法打开其他部管理的仓库？（同样只考虑钥匙的放置。）

    第一问很经典，就是打开将钥匙放入仓库构成一个环：1号仓库放2号钥匙，2号仓库放3号钥匙……n号仓库放1号钥匙。这种情况相当于钥匙和仓库编号构成一个圆排列方案数是$(n-1)!$种。

    而第二问就对应的将n个元素分成m个圆排列，方案数就是第一类无符号Stirling数$s(n,m)$。如要要考虑官员的情况，只需再乘上$n!$即可。

  2. 第二类Stirling数

    是集合的一个拆分，表示将n个不同的元素拆分成m个集合的方案数。

    可以从定义出发考虑第n+1个元素的情况，假设要把n+1个元素分成m个集合则分析如下：

    （1）如果n个元素构成了m-1个集合，那么第n+1个元素单独构成一个集合。方案数$f(n,m-1)$

    （2）如果n个元素已经构成了m个集合，将第n+1个元素插入到任意一个集合。方案数 $m*f(n,m)$ 。

    综合两种情况得：$f(n+1,m)=f(n,m-1)+m*f(n,m)$

    性质

    1. $s(n,0)=0^n$
    2. $s(n,n)=1$
    3. $s(n,1)=1$
    4. $s(n,n-1)=C(n,2)$
    5. $s(n,2)=2^{n-1}-1$
    6. $s(n,n-2)=C(n,3)+3C(n,4)$
    7. $s(n,3)={1\over 2}(3^{n-1}+1)-2^{n-1}$
    8. $s(n,n-3)=C(n,4)+10C(n,5)+15C(n,6)$
    9. $\sum\limits_{k=0}^{n}s(n,k)=B(n)$,$B(n)$是贝尔数

贝尔数

描述一个集合分割为若干个非空子集的方案数。

$B(0)=1$

$B(n+1)=\sum\limits_{k=0}^{n}B(k)$

格点线段

两个端点分别为(a,b),(c,d)则不计算端点，线上格点的个数为$gcd(d-b,c-a)-1$