n个球,m个盒子,每个盒子至少放一个球,方案数C(n - 1, m - 1) n >= m
n个球,m个盒子,允许有盒子不放球,方案数C(n + m - 1, m - 1) 等价于n + m 个球每个盒子至少放一个球的方案数
x + y = n 的方案数(x > 0, y > 0): n - 1种
x + y + z = n 的方案数(x > 0, y > 0, z > 0) : (n - 2) + (n - 3) + …… + 1 = (n - 1) * (n - 2) / 2
不定方程解的个数: 等价于n个球分成m份的方案数
x1 + x2 + x3 + …… xn <= n 等价于 x1 + x2 + x3 + …… + xn + z = n的方案数 其中z大于等于0
求gcd先变成绝对值
n种球共m个,每种球有a1,a2,a3……an个,则最后m个球的不同顺序数为C(m,a1) * C(m - a1,a2) * …… * C(m - a1 -.., an)
等同于 m! / (a1! * a2! * …… * an!)
a,b 互质, 若 (b * c) % a == 0 则 c % a = 0
a 在 mod m 下存在逆元当且仅当a与m互质
欧拉函数中当a,b互质时, ϕ(a * b) = ϕ(a) * ϕ(b),符合积性函数定义,可以用筛法O(n) 求1-n的欧拉函数 ϕ(1) = 0
当a为质数时,ϕ(a * b) = (a - 1) * ϕ(b)
欧拉定理: 当n与a互质时,则(a ^ ϕ(n)) mod n = 1
扩展欧拉定理: a ^ c ≡ a ^ (c % ϕ(m) + ϕ(m)) mod(m) if(c >= ϕ(m))
欧拉降幂:当n与a互质时,则a ^ b = (a ^ (b mod ϕ(n))) mod n
1-n的约数和: O(sqrt(n))
for(int l = 1 , r; l <= n ; l = r + 1)
{
r = n / (n / l) ; // 可以贡献(n / r)个数的区间为(l,r)
ans += (r - l + 1) * (n / r) ; 区间长 * 区间中每个数贡献的数
}
裴蜀定理(扩展欧几里得定理): 对于两个不全为0的整数a,b 存在两个整数x,y,使得 ax + by = gcd(a,b)
通解: a = a + k * b / gcd(a,b), b = b - k * a / gcd(a,b);
a的最小正整数解:
先乘对应倍数后 int t = abs(b/d); cout << (x % t + t) % t << endl;
中国剩余定理:
已知 x ≡ a1(mod m1)
x ≡ a2(mod m2)
x ≡ a3(mod m3)
……
x ≡ ak(mod mk)
其中m1,m2,m3……mk两两互质,找到x的最小非负解
M = m1 * m2 * …… mk , Mi = M / mi , Mi * ti = 1(mod mi)
x = Σ(ai * Mi * ti)
mi 与 Mi 互质,故 gcd(Mi,mi) = 1
所以 a * Mi + b * mi = gcd(Mi,mi) = 1 -> a * Mi = 1 - b * mi
在同余mi的情况下 a * Mi ≡ 1 (mod mi) ,故此时a即为Mi的逆元,为ti
for(int i = 1;i <= n;i++) scanf("%lld%lld",&m[i],&a[i]);
ll ans = 0;
ll M = 1;
for(int i = 1;i <= n;i++) M *= m[i];
for(int i = 1;i <= n;i++) mi[i] = M / m[i];
for(int i = 1;i <= n;i++)
{
ll x = 0, y = 0;
exgcd(mi[i],m[i],x,y);
while(x < 0) x += m[i];
ans += a[i] * mi[i] * x;
ans %= M;
}
cout << ans << endl;
扩展中国剩余定理:
中国剩余定理不能解决模数不互质的情况
k1 * m1 + a1 = k2 * m2 + a2 = x
k1 * m1 - k2 * m2 = a2 - a1
a2 - a1必须能整除 gcd(m1,m2),否则无解
用exgcd(m1,m2,x,y) 解出x * m1 + y * m2 = gcd(m1,m2) = d
k1 = x * (a2 - a1) / d
m2 对 d 的贡献:t = m2 / d
k1 = (k1 % t + t) % t
a1 = k1 * m1 + a1
m1 = abs(m1 / d * m2)
代码:
cin>>n;
cin>>m1>>a1;
bool has_anser = true;
for(int i = 0;i < n - 1;i++)
{
ll m2 = 0, a2 = 0, x = 0, y = 0;
scanf("%lld%lld",&m2,&a2);
ll d = exgcd(m1,m2,x,y);
if((a2 - a1) % d)
{
has_anser = false;
break;
}
x *= (a2 - a1) / d; // ll t = abs(m2 / d);
ll t = m2 / d; // ll v = ((a2 - a1) % m2 + m2) % m2;
x = (x % t + t) % t; // v /= d;
a1 = x * m1 + a1; //x = mul(x,v,t); // 龟速乘
m1 = abs(m1 / d * m2); // x = (x % t + t) % t;
}
if(!has_anser) puts("-1");
else cout << (a1 % m1 + m1) % m1 << endl;
return 0;
ll mul(ll a,ll b,ll c) // 龟速乘 a * b % p 防止爆long long
{
ll res=0;
while(b>0)
{
if(b&1)res=((res+a))%c;
a=(a+a)%c;
b>>=1;
}
return (res%c+c)%c;
}
错排问题:
错排问题指考虑一个有 n 个元素的排列,若一个排列中所有的元素都不在自己原来的位置上,那么这样的排列就称为原排列的一个错排。 n 个元素的错排数记为 D(n)
例如:n封信和n个信封,如果所有的信都装错了信封,求所有信都装错信封共有多少种不同情况。
把第 n 个元素放在一个位置,比如位置 k ,一共有 n−1 种方法;
放编号为k的元素,这时有两种情况:⑴把它放到位置 n ,那么,对于剩下的 n−1 个元素,由于第 k 个元素放到了位置 n ,剩下 n−2 个元素就有 D(n−2) 种方法;⑵第 k 个元素不把它放到位置 n ,这时,对于这 n−1 个元素,有 D(n−1) 种方法;
综上得到
D(n) = (n-1) *(D(n-2) + D(n-1))
特殊地,D(1) = 0, D(2) = 1
卡特兰数:
给定n个0和n个1,它们按照某种顺序排成长度为2n的序列,满足任意前缀中0的个数都不少于1的个数的序列的数量为:
Cat(n) = C(2n, n) / (n + 1)
= Cat(n – 1) * (4 * n - 2) / (n + 1);
若给n个0,m个1 则 方案数为 C(n + m,m) − C(n + m,n + 1)
O(n) 预处理逆元
void init() // O(n) 预处理逆元
{
fact[0] = infact[0] = fact[1] = infact[1] = 1;
for (int i = 2; i < N; i ++ )
{
fact[i] = (ll)fact[i - 1] * i % mod;
infact[i] = (ll)((ll)mod - mod / i) * infact[mod % i] % mod ;
}
for(int i = 2;i < N;i++) infact[i] = infact[i] * infact[i - 1] % mod;
}
ll c(int a,int b)
{
return fact[a] * infact[b] % mod * infact[a-b] % mod;
}
鸽巢原理
N + 1 只鸽子飞回N个鸽巢,至少有一个鸽巢有不少于两只鸽子
2N + 1只鸽子飞回N个鸽巢,至少有一个鸽巢有不少于三只鸽子
gcd(a1,a2,a3 …… an) = gcd(a1,a2 - a1,a3 - a2,……an - an - 1);
组合博弈:和NIM博弈结合 对称思想,完美匹配
巴什博弈:将第i堆必胜记为1,必败记为0,若所有异或和为0,则必败,否则必胜