不可重复排列数 n ! ( n − r ) ! frac{n!}{(n-r)!} (n−r)!n!
可重复排列数 n r n^r nr
圆排列数 n ! r ( n − r ) ! frac{n!}{r(n-r)!} r(n−r)!n!
无限多重集排列，k个不同元素 k r k^r kr
有限多重集排列，k个不同元素 n ! n 1 ! n 2 ! . . . n k ! frac{n!}{n_1!n_2!...n_k!} n1!n2!...nk!n!
无限多重集组合，k个不同元素 C r + k − 1 r C_{r+k-1}^r Cr+k−1r
n+1只鸽子住n个巢，至少有一个巢里有至少2只鸽子
kn+1只鸽子住n个巢，至少有一个巢里有至少k+1只鸽子
如果将 q 1 + q 2 + . . . q n − n + 1 q_1+q_2+...q_n-n+1 q1+q2+...qn−n+1个物体放入n个盒子，那么或者第1个盒子至少有 q 1 q_1 q1个物体,或者第2个盒子至少有 q 2 q_2 q2个物体,…,或者第n个盒子至少有 q n q_n qn个物体
Ramsey定理：在6人（或更多）中，或者有3人，每两人都互相认识，或者有3人，每两人都不认识
C n r = ( n r ) = n ! r ! ( n − r ) ! C_n^r=binom{n}{r}=frac{n!}{r!(n-r)!} Cnr=(rn)=r!(n−r)!n!
杨辉三角第n+1行第r+1列数， ( 1 + x ) n (1+x)^n (1+x)n展开后第r+1项系数
( a + b ) n = ∑ r = 0 n C n r a r b n − r (a+b)^n=sumlimits_{r=0}^nC_n^ra^rb^{n-r} (a+b)n=r=0∑nCnrarbn−r
C n r = C n − 1 r − 1 + C n − 1 r C_n^r=C_{n-1}^{r-1}+C_{n-1}^r Cnr=Cn−1r−1+Cn−1r
C n 0 + C n 1 + . . . + C n n = 2 n C_n^0+C_n^1+...+C_n^n=2^n Cn0+Cn1+...+Cnn=2n
#include<bits/stdc++.h>
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==0) c[i][j] = 1;else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
}
int main(){int n;init();scanf("%d", &n);while (n -- ){int a, b;scanf("%d%d", &a, &b);printf("%dn", c[a][b]);}return 0;
}
预处理 O ( n ) O(n) O(n)
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod = 998244353;
const ll N = 1e6 + 10;
ll jc[N], jcn[N],inv[N];;
//ll ksm(ll a, ll b) {
// ll res = 1;
// a = a % mod;
// while (b) {
// if (b & 1) res = (res * a) % mod;
// a = (a * a) % mod;
// b >>= 1;
// }
// return res;
//}
//费马小定理
//ll ny(ll x) {
// return ksm(x, mod - 2);
//}
void pre_ny(ll n, ll p) {inv[1] = 1;for (ll i = 2; i <= n; i++) inv[i] = (p - p / i) * (inv[p % i]) % p;//线性求逆元
}
ll C(ll n, ll m) {return jc[n] * jcn[m] % mod * jcn[n - m] % mod;
}
int main() {pre_ny(N, mod);jc[0] = jcn[0] = 1;for (ll i = 1; i <= N; i++) {jc[i] = (jc[i - 1] * i) % mod;jcn[i] = (jcn[i - 1] * inv[i]) % mod;}ll t, n, m;cin>>t;while (t--) {cin >> n >> m;cout<< C(n, m)<<'n';}return 0;
}
对于质数 p，有
C n r ≡ C n m o d p r m o d p ⋅ C n / p r / p ( m o d p ) C_n^requiv C_{n mod p}^{r mod p}cdot C_{n/p}^{r/p}(mod p) Cnr≡Cn mod pr mod p⋅Cn/pr/p(mod p)
P3807 【模板】卢卡斯定理/Lucas 定理
给定整数 n , m , p n, m, p n,m,p 的值，求出 C n + m n m o d p C_{n + m}^n bmod p Cn+mnmodp 的值。
输入数据保证 p p p 为质数。
注: C C C 表示组合数。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define P pair<int,int>
const double eps = 1e-8;
const ll INF = 1e18;
const ll N = 1e5 + 10;
const ll mod = 1e9 + 7;
ll jc[N];
ll ksm(ll a, int b, int p) {a %= p;ll res = 1;while (b) {if (b & 1) res = (res * a) % p;a = (a * a) % p;b >>= 1;}return res;
}
ll C(int n, int r, int p) {if (r > n) return 0;return jc[n] * ksm(jc[r], p - 2, p) % p * ksm(jc[n - r], p - 2, p) % p;
}
ll lucas(int n, int r, int p) {if (r == 0) return 1;return C(n % p, r % p, p) * lucas(n / p, r / p, p) % p;
}
void solve() {int n, m, p;cin >> n >> m >> p;jc[0] = 1;for (int i = 1; i <= p; ++i) jc[i] = (jc[i - 1] * i) % p;cout << lucas(n + m, n, p) << 'n';
}
int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int _t;//_t = 1;cin >> _t;while (_t--) {solve();}return 0;
}
{ C n m m o d p 1 α 1 C n m m o d p 2 α 2 . . . . . . left{begin{aligned}C_n^m bmod {p_1^{alpha_1}} \C_n^m bmod {p_2^{alpha_2}}\ ......end{aligned} right. ⎩ ⎨ ⎧Cnmmod p1α1Cnmmod p2α2......
= n ! P x m ! P y ( n − m ) ! P z P x − y − z m o d P k =frac {frac {n!}{P^{x}}}{frac {m!}{P^{y}}frac {(n-m)!}{P^{z}}}P^{x-y-z}bmod{P^k} =Pym!Pz(n−m)!Pxn!Px−y−zmodPk
= f ( n ) f ( m ) f ( n − m ) P g ( n ) − g ( m ) − g ( n − m ) m o d P k =frac {f(n)}{f(m)f(n-m)}P^{g(n)-g(m)-g(n-m)}bmod{P^k} =f(m)f(n−m)f(n)Pg(n)−g(m)−g(n−m)modPk
f ( n ) = f ( ⌊ n P ⌋ ) ( ∏ i = 1 , i ≢ 0 ( m o d P ) P k i ) ⌊ n P k ⌋ ( ∏ i = P k ⌊ n P k ⌋ , i ≢ 0 ( m o d P ) n i ) f(n)=f(lfloor frac nPrfloor)(prodlimits_{i=1,inotequiv 0pmod {P}}^{P^k}i)^{lfloor frac n{P^k}rfloor}(prodlimits_{i=P^klfloor frac n{P^k}rfloor,inotequiv 0pmod {P}}^ni) f(n)=f(⌊Pn⌋)(i=1,i≡0(modP)∏Pki)⌊Pkn⌋(i=Pk⌊Pkn⌋,i≡0(modP)∏ni)
g ( n ) = ⌊ n P ⌋ + g ( ⌊ n P ⌋ ) g(n)=lfloor frac nPrfloor+g(lfloor frac nPrfloor) g(n)=⌊Pn⌋+g(⌊Pn⌋)
P4720 【模板】扩展卢卡斯定理/exLucas
求 C n m m o d p {mathrm{C}}_n^m bmod{p} Cnmmodp
其中 C mathrm{C} C 为组合数。
O ( log P n ) O(log_Pn) O(logPn)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define P pair<int,int>
const double eps = 1e-8;
const ll mod = 1e9 + 7;
const ll INF = 1e18;
const ll N = 1e5 + 10;
ll n, m, p;
ll prime[N], cnt, c[N];
ll ksm(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;
}
ll exgcd(ll a, ll b, ll& x, ll& y) {if (!b) {x = 1, y = 0;return a;}ll t = exgcd(b, a % b, x, y);ll x0 = x, y0 = y;x = y0;y = x0 - a / b * y0;return t;
}
ll ny(ll n, ll p) {ll x, y;exgcd(n, p, x, y);return (x % p + p) % p;
}
ll f(ll n, ll p, ll pr) {if (n == 0) return 1;ll rou = 1, rem = 1;for (ll i = 1; i <= p; ++i) {if (i % pr) rou = rou * i % p;}rou = ksm(rou, n / p, p);for (ll i = p * (n / p); i <= n; ++i) {if (i % pr) rem = rem * (i % p) % p;}return f(n / pr, p, pr) * rou % p * rem % p;
}
ll g(ll n, ll p) {if (n < p) return 0;return g(n / p, p) + n / p;
}
ll C(ll n, ll m, ll p, ll pr) {ll fz = f(n, p, pr), fm1 = ny(f(m, p, pr), p), fm2 = ny(f(n - m, p, pr), p);ll pp = ksm(pr, g(n, pr) - g(m, pr) - g(n - m, pr), p);return fz * fm1 % p * fm2 % p * pp % p;
}
void getprime(int x) {for (ll i = 2; i * i <= x; ++i) {if (x % i == 0) {ll res = 1;while (x % i == 0) {res *= i;x /= i;}prime[++cnt] = res;c[cnt] = C(n, m, res, i);}}if (x != 1) {prime[++cnt] = x;c[cnt] = C(n, m, x, x);}
}
ll exlucas(ll n, ll m, ll p) {getprime(p);ll ans = 0;for (ll i = 1; i <= cnt; ++i) {ll m = p / prime[i], inv = ny(m, prime[i]);ans = (ans + c[i] * m % p * inv % p) % p;}return ans;
}
void solve() {cin >> n >> m >> p;cout << exlucas(n, m, p);
}
int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int _t;_t = 1;//cin>>_t;while (_t--) {solve();}return 0;
}
∣ A 1 ∪ A 2 ∪ . . . ∪ A n ∣ = ∑ ∣ A i ∣ − ∑ ∣ A i ∩ A j ∣ + ∑ ∣ A i ∩ A j ∩ A k ∣ + . . . + ( − 1 ) n + 1 ∣ A 1 ∩ A 2 ∩ . . . ∩ A n ∣ |A_1cup A_cup A_n|=sum|A_i|-sum|A_icap A_j|+sum|A_icap A_jcap A_k|+...+(-1)^{n+1}|A_1cap A_cap A_n| ∣A1∪A2∪...∪An∣=∑∣Ai∣−∑∣Ai∩Aj∣+∑∣Ai∩Aj∩Ak∣+...+(−1)n+1∣A1∩A2∩...∩An∣
C n = 1 n + 1 ( 2 n n ) C_n=frac{1}{n+1}binom{2n}{n} Cn=n+11(n2n)
C n = ( 2 n n ) − ( 2 n n − 1 ) C_n=binom{2n}{n}-binom{2n}{n-1} Cn=(n2n)−(n−12n)
C n = C 0 C n − 1 + C 1 C n − 2 + . . . + C n − 2 C 1 + C n − 1 C 0 = ∑ C k C n − k , C 0 = 1 C_n=C_0C_{n-1}+C_1C_{n-2}+...+C_{n-2}C_1+C_{n-1}C_0=sum C_kC_{n-k},C_0=1 Cn=C0Cn−1+C1Cn−2+...+Cn−2C1+Cn−1C0=∑CkCn−k,C0=1
C n = 4 n − 2 n + 1 C n − 1 , C 0 = 1 C_n=frac{4n-2}{n+1}C_{n-1},C_0=1 Cn=n+14n−2Cn−1,C0=1
把n个1和n个0排成一行，使任意前k个数中1的数量总大于等于0的数量的排列数量
应用：
1.棋盘问题（路径问题）
2.括号问题（出栈序列问题）
3.二叉树问题
4.三角剖分问题：n+1条边凸多边形划分三角形，有 C n − 1 C_{n-1} Cn−1种方案
s ( n , k ) , [ n k ] : s(n,k),{nbrack k}: s(n,k),[kn]: 把n个不同元素分配到k个圆排列里的方案数
升阶函数各项系数
[ n k ] = [ n − 1 k − 1 ] + ( n − 1 ) [ n − 1 k ] {nbrack k}={n-1brack k-1}+(n-1){n-1brack k} [kn]=[k−1n−1]+(n−1)[kn−1]
s ( 0 , 0 ) = 1 s(0,0)=1 s(0,0)=1
s ( n , 0 ) = 0 s(n,0)=0 s(n,0)=0
s ( n , n ) = 1 s(n,n)=1 s(n,n)=1
s ( n , 1 ) = ( n − 1 ) ! s(n,1)=(n-1)! s(n,1)=(n−1)!
s ( n , 2 ) = ( n − 1 ) ! ∑ i = 1 n − 1 1 i s(n,2)=(n-1)!sumlimits_{i=1}^{n-1}frac{1}{i} s(n,2)=(n−1)!i=1∑n−1i1
s ( n , n − 1 ) = C n 2 s(n,n-1)=C_n^2 s(n,n−1)=Cn2
s ( n , n − 2 ) = 2 C n 3 + 3 C n 4 s(n,n-2)=2C_n^3+3C_n^4 s(n,n−2)=2Cn3+3Cn4
∑ k = 0 n s ( n , k ) = n ! sumlimits_{k=0}^ns(n,k)=n! k=0∑ns(n,k)=n!
S ( n , k ) , { n k } : S(n,k),{nbrace k}: S(n,k),{kn}: 把n个不同元素拆分成k个集合的方案数
{ n k } = { n − 1 k − 1 } + k { n − 1 k } {nbrace k}={n-1brace k-1}+k{n-1brace k} {kn}={k−1n−1}+k{kn−1}
S ( n , m ) = 1 m ! ∑ k = 0 m ( − 1 ) k ( m k ) ( m − k ) n S(n,m)=frac{1}{m!}sumlimits_{k=0}^m(-1)^kbinom{m}{k}(m-k)^n S(n,m)=m!1k=0∑m(−1)k(km)(m−k)n
S ( n , 0 ) = 0 n S(n,0)=0^n S(n,0)=0n
S ( n , n ) = 1 S(n,n)=1 S(n,n)=1
S ( n , 1 ) = 1 S(n,1)=1 S(n,1)=1
S ( n , 2 ) = 2 n − 1 − 1 S(n,2)=2^{n-1}-1 S(n,2)=2n−1−1
S ( n , n − 1 ) = C n 2 S(n,n-1)=C_n^2 S(n,n−1)=Cn2
S ( n , n − 2 ) = C n 3 + 3 C n 4 S(n,n-2)=C_n^3+3C_n^4 S(n,n−2)=Cn3+3Cn4
∑ k = 0 n S ( n , k ) = B n , B n sumlimits_{k=0}^nS(n,k)=B_n,B_n k=0∑nS(n,k)=Bn,Bn是贝尔数
∑ k = 0 n { n k } [ k m ] = ∑ k = 0 n [ n k ] { k m } sumlimits_{k=0}^n{nbrace k}{kbrack m}=sumlimits_{k=0}^n{nbrack k}{kbrace m} k=0∑n{kn}[mk]=k=0∑n[kn]{mk}
B n B_n Bn的含义是基数为 n 的集合划分成非空集合的划分数
B 0 = 1 B_0=1 B0=1
B n + 1 = ∑ k = 0 n ( n k ) B k B_{n+1}=sumlimits_{k=0}^nbinom{n}{k}B_k Bn+1=k=0∑n(kn)Bk
B n = ∑ k = 0 n S ( n , k ) B_n=sumlimits_{k=0}^nS(n,k) Bn=k=0∑nS(n,k)
第一行第一项为 1 ( a 1 , 1 = 1 ) (a_{1,1}=1) (a1,1=1)；
对于 n>1，第 n 行第一项等于第 n-1 行的第 n - 1 项 ( a n , 1 = a n − 1 , n − 1 ) (a_{n,1}=a_{n-1,n-1}) (an,1=an−1,n−1)；
对于 m,n>1，第 n 行的第 m 项等于它左边和左上角两个数之和 ( a n , m = a n , m − 1 + a n − 1 , m − 1 ) (a_{n,m}=a_{n,m-1}+a_{n-1,m-1}) (an,m=an,m−1+an−1,m−1)
每行的首项是贝尔数。
D n = ( n − 1 ) ( D n − 1 + D n − 2 ) D_n=(n-1)(D_{n-1}+D_{n-2}) Dn=(n−1)(Dn−1+Dn−2)
D n = n ! ∑ k = 0 n ( − 1 ) k k ! D_n=n!sumlimits_{k=0}^nfrac{(-1)^k}{k!} Dn=n!k=0∑nk!(−1)k
置换的合成运算 g ∘ f ( k ) = g ( f ( k ) ) gcirc f(k)=g(f(k)) g∘f(k)=g(f(k))
置换的逆 f − 1 ∘ f = τ f^{-1}circ f=tau f−1∘f=τ， τ tau τ为恒等置换
设G是S的置换群，f是G中的一个置换，设 λ ( f ) lambda(f) λ(f)为置换f中不变元的个数，则置换群G的着色方法数为 1 ∣ G ∣ ∑ f ∈ G ∣ λ ( f ) ∣ frac{1}{|G|}sumlimits_{fin G}|lambda(f)| ∣G∣1f∈G∑∣λ(f)∣
P1446 [HNOI2008] Cards
小春现在很清闲，面对书桌上的 n n n 张牌，他决定给每张牌染色，目前小春拥有 3 3 3 种颜色：红色，蓝色，绿色。他询问 Sun 有多少种染色方案，Sun 很快就给出了答案。
进一步，小春要求染出 S r S_r Sr 张红色， S b S_b Sb 张蓝色， S g S_g Sg 张绿色。他又询问有多少种方案，Sun 想了一下，又给出了正确答案。最后小春发明了 m m m 种不同的洗牌法，这里他又问 Sun 有多少种不同的染色方案。两种染色方法相同当且仅当其中一种可以通过任意的洗牌法（即可以使用多种洗牌法，而每种方法可以使用多次）洗成另一种。
Sun 发现这个问题有点难度，决定交给你，由于答案可能很大，你只需要求出答案对于 P P P 取模的结果。 保证 P P P 为一个质数。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define P pair<int,int>
const double eps = 1e-8;
const ll mod = 1e9 + 7;
const ll INF = 1e18;
const ll N = 1e5 + 10;
int sr, sb, sg, n, m, p, ans;
int a[100], vis[100], siz[100], dp[25][25][25];
ll ksm(ll a, ll b) {a %= p;ll res = 1;while (b) {if (b & 1) res = res * a % p;a = a * a % p;b >>= 1;}return res;
}
int calc() {memset(dp, 0, sizeof(dp));memset(vis, 0, sizeof(vis));int cnt = 0;for (int i = 1; i <= n; ++i) {if (!vis[i]) {int p = i, len = 0;while (!vis[p]) {len++;vis[p] = 1;p = a[p];}siz[++cnt] = len;}}dp[0][0][0] = 1;for (int i = 1; i <= cnt; ++i) {for (int r = sr; r>=0; --r) {for (int b = sb; b>=0; --b) {for (int g = sg; g>=0; --g) {if (r >= siz[i]) dp[r][b][g] = (dp[r][b][g] + dp[r - siz[i]][b][g]) % p;if (b >= siz[i]) dp[r][b][g] = (dp[r][b][g] + dp[r][b - siz[i]][g]) % p;if (g >= siz[i]) dp[r][b][g] = (dp[r][b][g] + dp[r][b][g - siz[i]]) % p;}}}}return dp[sr][sb][sg];
}
void solve() {cin >> sr >> sb >> sg >> m >> p;n = sr + sb + sg;for (int i = 1; i <= m; ++i) {for (int j = 1; j <= n; ++j) {cin >> a[j];}ans = (ans + calc()) % p;}for (int i = 1; i <= n; ++i) a[i] = i;ans = (ans + calc()) % p;cout << ans * ksm(m + 1, p - 2) % p;
}
int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int _t;_t = 1;//cin>>_t;while (_t--) {solve();}return 0;
}
任何一种置换都能表示成若干互不相交的循环的乘积。
在一种置换中，用 λ i ( f ) lambda_i(f) λi(f) 表示长度为 i 的循环的个数，用 λ ( f ) lambda(f) λ(f)表示 f ∈ G fin G f∈G中循环的个数。
设 G = { f 1 , f 2 , . . . , f n } G={f_1,f_2,...,f_n} G={f1,f2,...,fn}是 S n S_n Sn是置换群，用 m 种颜色对 n 个对象着色，G的着色方法数为 1 ∣ G ∣ ∑ f ∈ G m λ ( f ) = 1 ∣ G ∣ ∑ f ∈ G m λ 1 ( f ) + λ 2 ( f ) + . . . + λ n ( f ) frac{1}{|G|}sumlimits_{fin G}m^{lambda(f)}=frac{1}{|G|}sumlimits_{fin G}m^{lambda_1(f)+lambda_2(f)+...+lambda_n(f)} ∣G∣1f∈G∑mλ(f)=∣G∣1f∈G∑mλ1(f)+λ2(f)+...+λn(f)
第 i 个旋转的循环节数为 g c d ( n , i ) , 0 ≤ i < n gcd(n,i),0le i<n gcd(n,i),0≤i<n
若 n 为偶数，经过多边形顶点的对称轴有n/2个，即n/2种置换，每种置换方案有n/2+1个循环节；不经过顶点的对称轴有n/2个，每种置换方案有n/2个循环节
若 n 为奇数，对称轴都经过顶点，有n种置换，每种置换有n/2+1个循环节
P4980 【模板】Pólya 定理
给定一个 n n n 个点， n n n 条边的环，有 n n n 种颜色，给每个顶点染色，问有多少种本质不同的染色方案，答案对 1 0 9 + 7 10^9+7 109+7 取模
注意本题的本质不同，定义为：只需要不能通过旋转与别的染色方案相同。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define P pair<int,int>
const double eps = 1e-8;
const ll mod = 1e9 + 7;
const ll INF = 1e18;
const ll N = 1e5 + 10;
ll getphi(ll n) {ll res = n;for (ll i = 2; i*i<=n; ++i) {if (n % i == 0) {res = res / i * (i - 1);while (n % i == 0) n /= i;}}if (n > 1) res = res / n * (n - 1);return res;
}
ll ksm(ll a, ll b) {a %= mod;ll res = 1;while (b) {if (b & 1) res = (res * a) % mod;a = (a * a) % mod;b >>= 1;}return res;
}
void solve() {ll n,ans=0;cin >> n;for (ll i = 1; i * i <= n; ++i) {if (n % i == 0) {ans = (ans + getphi(i) * ksm(n, n / i - 1)) % mod;if (i * i != n) ans = (ans + getphi(n / i) * ksm(n, i - 1)) % mod;}}cout << ans << 'n';
}
int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int _t;//_t = 1;cin>>_t;while (_t--) {solve();}return 0;
}
生成函数的定义： g ( x ) = a 0 + a 1 x + a 2 x 2 + a 3 x 3 + . . . g(x)=a_0+a_1x+a_2x^2+a_3x^3+... g(x)=a0+a1x+a2x2+a3x3+....称g(x)是序列 a 0 , a 1 , a 2 , . . . a_0,a_1,a_2,... a0,a1,a2,...的生成函数，x 充当形式参数没有意义。
普通生成函数：k 种元素的多重集合的 r 组合数（有限和无限多重集都可以）
指数生成函数：k 种元素的多重集合的 r 排列数（有限和无限多重集都可以）
列出式子，有 n 项，每项代表一个种类的限制（一个括号代表一项），共取 m 个，生成函数为 g ( x ) = ( 1 + x + x 2 + … ) ( 1 + x 2 + x 4 + … ) ( 1 + x 3 + x 6 + … ) … g(x)=(1+x+x^2+dots)(1+x^2+x^4+dots)(1+x^3+x^6+dots)dots g(x)=(1+x+x2+…)(1+x2+x4+…)(1+x3+x6+…)…计算 x m x^m xm 的系数，化为分式，二项式展开。
1 ( 1 − x ) n = ∑ k = 0 ∞ C n + k − 1 k x k frac{1}{(1-x)^n}=sumlimits_{k=0}^infty C_{n+k-1}^kx^k (1−x)n1=k=0∑∞Cn+k−1kxk
1 1 − x = 1 + x + x 2 + x 3 + . . . frac{1}{1-x}=1+x+x^2+x^3+... 1−x1=1+x+x2+x3+...
1 1 − x 6 = 1 + x 6 + x 12 + . . . frac{1}{1-x^6}=1+x^6+x^{12}+... 1−x61=1+x6+x12+...
1 − x 6 1 − x = 1 + x + x 2 + x 3 + x 4 + x 5 frac{1-x^6}{1-x}=1+x+x^2+x^3+x^4+x^5 1−x1−x6=1+x+x2+x3+x4+x5
x ( 1 − x ) 2 = x + 2 x 2 + 3 x 3 + . . . frac{x}{(1-x)^2}=x+2x^2+3x^3+... (1−x)2x=x+2x2+3x3+...
e x = 1 + 1 1 ! x + 1 2 ! x 2 + 1 3 ! x 3 + . . . e^x=1+frac{1}{1!}x+frac{1}{2!}x^2+frac{1}{3!}x^3+... ex=1+1!1x+2!1x2+3!1x3+...
e 2 x = 1 + 1 1 ! 2 x + 1 2 ! ( 2 x ) 2 + 1 3 ! ( 2 x ) 3 + . . . e^{2x}=1+frac{1}{1!}2x+frac{1}{2!}(2x)^2+frac{1}{3!}(2x)^3+... e2x=1+1!12x+2!1(2x)2+3!1(2x)3+...
P5367 【模板】康托展开
对于一个1到n的排列{a1 ,a2 ,⋯,an }，比它小的排列有 ∑ i = 1 n s u m a i × ( n − i ) ! sumlimits_{i=1}^nsum_{a_i}times(n-i)! i=1∑nsumai×(n−i)!个
s u m a i sum_{a_i} sumai为在 ai 后面的元素里比它小的元素个数，即 ∑ j = 1 n ( a j < a i ) sumlimits_{j=1}^n(a_j<a_i) j=1∑n(aj<ai)，树状数组求解
逆康托展开
类似于进制转换，不断 %(n-i)! ，/(n-i)!就可以得到sum数组，然后就可以还原出原排列。
HDU - 1846 Brave Game
各位勇敢者要玩的第一个游戏是什么呢？很简单，它是这样定义的：
1、 本游戏是一个二人游戏;
2、 有一堆石子一共有n个；
3、 两人轮流进行;
4、 每走一步可以取走1…m个石子；
5、 最先取光石子的一方为胜；
如果游戏的双方使用的都是最优策略，请输出哪个人能赢。
结论：被(m+1)整除，先手败
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define P pair<int,int>
const double eps = 1e-8;
const ll INF = 1e18;
const ll N = 1e5 + 10;
void solve() {int n;cin >> n;for (int i = 1; i <= n; ++i) {int x, y;cin >> x >> y;if (x % (y + 1)==0) cout << "secondn";else cout << "firstn";}
}
int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int _t;_t = 1;//cin >> _t;while (_t--) {solve();}return 0;
}
P2197 【模板】nim 游戏
甲，乙两个人玩 nim 取石子游戏。
nim 游戏的规则是这样的：地上有 n n n 堆石子（每堆石子数量小于 1 0 4 10^4 104），每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取。每次只能从一堆里取。最后没石子可取的人就输了。假如甲是先手，且告诉你这 n n n 堆石子的数量，他想知道是否存在先手必胜的策略。
结论：异或和为0，先手败
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define P pair<int,int>
const double eps = 1e-8;
const ll INF = 1e18;
const ll N = 1e5 + 10;
void solve() {int ans = 0, n;cin >> n;for (int i = 1; i <= n; ++i) {int a;cin >> a;ans ^= a;}if (ans) cout << "Yesn";else cout << "Non";
}
int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int _t;//_t = 1;cin>>_t;while (_t--) {solve();}return 0;
}
AcWing 892. 台阶-Nim游戏
现在，有一个n级台阶的楼梯，每级台阶上都有若干个石子，其中第i级台阶上有 a i a_i ai个石子(i≥1)。
两位玩家轮流操作，每次操作可以从任意一级台阶上拿若干个石子放到下一级台阶中（不能不拿）。
已经拿到地面上的石子不能再拿，最后无法进行操作的人视为失败。
问如果两人都采用最优策略，先手是否必胜。
结论：当奇数级阶梯的石子数量异或和为0,先手必败，否则先手必胜。
P2252 [SHOI2002]取石子游戏|【模板】威佐夫博弈
有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。
结论：等于(b-a)*1.618，先手败
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define P pair<int,int>
const double eps = 1e-8;
const ll INF = 1e18;
const ll N = 1e5 + 10;
void solve() {int a, b;cin >> a >> b;double temp = (sqrt(5) + 1) / 2;if (a > b) swap(a, b);if (a == int((b - a) * temp)) cout << 0;else cout << 1;
}
int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int _t;_t = 1;//cin >> _t;while (_t--) {solve();}return 0;
}
有一堆个数为n(n>=2)的石子，游戏双方轮流取石子，规则如下：
1)先手不能在第一次把所有的石子取完，至少取1颗；
2)之后每次可以取的石子数至少为1，至多为对手刚取的石子数的2倍。
约定取走最后一个石子的人为赢家，求必败态。
结论：当n为斐波那契数时，先手必败。
P-position为前一个玩家的必胜位置，N-position为下一个玩家的必胜位置
sg(x)等于x所有后缀sg值中未出现过的最小非负整数
SG函数实现巴什博弈，sg(x)=0的点是必败点
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define P pair<int,int>
const double eps = 1e-8;
const ll mod = 1e9 + 7;
const ll INF = 1e18;
const ll N = 1e3 + 10;
int n, m, sg[N], s[N];
void getsg() {memset(sg, 0, sizeof(sg));for (int i = 1; i <= n; ++i) {memset(s, 0, sizeof(s));for (int j = 1; j <= m && i >= j; ++j) s[sg[i - j]] = 1;for (int j = 0; j <= n; ++j) {if (!s[j]) {sg[i] = j;break;}}}
}
void solve() {cin >> n >> m;getsg();if (sg[n]) cout << "firstn";else cout << "secondn";
}
int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int _t;//_t = 1;cin>>_t;while (_t--) {solve();}return 0;
}
本文发布于:2024-01-27 20:50:00，感谢您对本站的认可！
本文链接：https://www.4u4v.net/it/17063597992555.html
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，我们将在24小时内删除。
| 留言与评论（共有 0 条评论） |
