生成函数
HDU 1171
题意：给你ｎ种物品(n≤50)，每种物品价值为ｖ(v≤50) ,不超过m个(m≤100)，将这些物品分配给两个人，使得两人各自物品价值和尽可能接近，输出两人各自物品价值和
思路：构造ｎ个多项式，第ｉ个多项式的ｋ×ｖ[i] 位为１，其余全为０(0 ≤ k ≤ m)，乘起来，取最接近总和的一半，且系数不为０的项的幂次作为答案。
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 using namespace std; 5 set<int>st; 6 int c1[250005],c2[250005],n; 7 int a[55],b[55]; 8 int main() { 9 while(scanf("%d",&n)!=EOF && n>=0) { 10 memset(c1,0,sizeof(c1)); 11 for(int i = 1; i <= n;i++) scanf("%d%d", &a[i], &b[i]); 12 c1[0] = 1; 13 int s = 0; 14 for(int i = 1;i <= n;i++) { 15 s += a[i]*b[i]; 16 for(int j = 0;j <= s;j++) 17 for(int k = 0,kk = 0; j + k <= s && kk <= b[i]; k += a[i], kk++) 18 c2[j + k] += c1[j]; 19 for(int j = 0; j <= s;j++) { 20 c1[j] = c2[j]; 21 c2[j] = 0; 22 } 23 } 24 int ans; 25 for(ans = s/2;ans >0 && c1[ans] ==0;ans--); 26 printf("%d %d\n",s-ans,ans); 27 } 28 }
其余类似的题目：
#include <bits/stdc++.h> using namespace std; const int N = 105; int a[N], b[N], n, m; int c1[N], c2[N]; int main() { while(scanf("%d%d", &n, &m) != EOF) { for(int i = 1; i <= n; i++) scanf("%d%d", &a[i], &b[i]); memset(c1, 0, sizeof(c1)); memset(c2, 0, sizeof(c2)); for(int i = a[1]; i <= b[1]; i++) c1[i] = 1; for(int i = 2; i <= n; i++) { for(int j = 0; j <= m; j++) { for(int k = a[i];k + j <= m && k <= b[i]; k++) c2[k + j] += c1[j]; for(int j = 0; j <= m; j++){ c1[j] = c2[j]; c2[j] = 0; } } printf("%d\n", c1[m]); } }
#include <bits/stdc++.h> using namespace std; int a[5],sum[5],d[5]; int c1[10001], c2[10001]; int main() { while(scanf("%d%d%d", &a[1], &a[2], &a[3]) != EOF &&(a[1] || a[2] || a[3])) { sum[2] = a[1] + a[2] * 2; sum[3] = sum[2] + a[3] * 5; d[2] = 2,d[3] = 5; memset(c1, 0, sizeof(c1)); memset(c2, 0, sizeof(c2)); for(int i = 0;i <= a[1]; i++) c1[i] = 1, c2[i] = 0; for(int i = 2;i <= 3; i++) { for(int j = 0;j <= sum[i]; j++){ for(int k = 0,kk = 0;k + j <= sum[i]&&kk <= a[i];k += d[i], kk++) { c2[j + k] += c1[j]; } } for(int j = 0;j <= sum[i]; j++) c1[j] = c2[j], c2[j] = 0; } int ans = sum[3]+1; for(int i = 0;i <= sum[3];i++) { if(c1[i] == 0) {ans = i; break;} } printf("%d\n", ans); } }
#include <cstdio> #include <iostream> using namespace std; const int M = 10001; int c1[M], c2[M]; int main() { int n; while(scanf("%d", &n) != EOF && n) { for(int i = 0; i <= n; i++) c1[i] = 1, c2[i] = 0; for(int i = 2; i <= 17; i++) { if(i*i>n)break; for(int j = 0; j <= n; j++) for(int k = 0; k + j <= n; k += (i*i) ) c2[j+k] += c1[j]; for(int j = 0; j <= n; j++) c1[j] = c2[j], c2[j] = 0; // for(int j = 0; j <= n; j++) cout << c1[j] <<" "; // cout<<'\n'; } printf("%d\n", c1[n]); } }
##includeinclude <iostream><iostream> usingusing namespacenamespace stdstd; ; constconst intint M = M = 1000110001; ; intint c1[M], c2[M]; c1[M], c2[ int main() { int n; while(scanf("%d", &n) != EOF) { for(int i = 0; i <= n; i++) c1[i] = 1, c2[i] = 0; for(int i = 2; i <= n; i++) { for(int j = 0; j <= n; j++) for(int k = 0; k + j <= n; k += i) c2[j+k] += c1[j]; for(int j = 0; j <= n; j++) c1[j] = c2[j], c2[j] = 0; } printf("%d\n", c1[n]); } }
HDU 1521
题意：ｎ种物品，每种物品a[i]个,涌中选出ｍ个，求排列数
思路：指数型生成函数裸题，用到分数类
#include <bits/stdc++.h> using namespace std; typedef long long ll; struct cre { ll fz,fm; cre operator * (const cre &o) const{ ll z = fz * o.fz; ll m = fm * o.fm; ll _ = __gcd(z, m); return (cre){z/_, m/_}; } cre operator + (const cre &o) const{ ll z = fz * o.fm + o.fz * fm; ll m = fm * o.fm; ll _ = __gcd(z, m); return (cre){z/_, m/_}; } }; int jc[11]; int n, m, a[11]; cre c1[101], c2[101],tmp[101]; void ycl() { jc[0] = jc[1] = 1; for(int i = 2; i <= 10; i++) jc[i] = jc[i-1]*i; } int main() { ycl(); while(scanf("%d%d", &n, &m)!=EOF) { for(int i = 1; i <= n; i++) scanf("%d", &a[i]); for(int i = 0; i <= a[1]; i++) c1[i] = (cre){1,jc[i]},c2[i] = cre{0,1}; for(int i = a[1]+1; i <= m; i++) c1[i] = c2[i] = (cre){0,1}; for(int i = 2; i <= n; i++) { for(int j = 0; j <= a[i]; j++) tmp[j] = (cre){1,jc[j]}; for(int j = a[i]+1;j <= m;j++) tmp[j] = (cre){0,1}; for(int j = 0; j <= m; j++) { for(int k = 0; k <= a[i] && k+j <=m; k++){ c2[j + k] = c2[j + k] + (tmp[k] * c1[j]); } } for(int j = 0; j <= m; j++) { c1[j] = c2[j]; c2[j] = {0,1}; } } if(c1[m].fm < jc[m]) { int bs = jc[m] / c1[m].fm; printf("%lld\n", c1[m].fz * bs); } else { int bs = c1[m].fm / jc[m]; printf("%lld\n", c1[m].fz / bs); } } }
Polya计数定理
POJ2154
题意：Ｎ个珠子串成环，用Ｎ种颜色染色，旋转重合视为一种，输出不同染色方案对Ｐ取模的答案
思路：对于某一种置换——旋转x个单位，循环节数量 m = gcd(x,N)，方案数 = N ^ m，考虑将m相同的分组，
gcd(x,N) == k 则 gcd(x/k,N/k) == 1，数量为phi(n/k) ,可以枚举Ｎ的因子。
最后要除以置换数Ｎ，但这里的Ｐ不一定是质数，可以在求方案数的时候的幂次减少１
#include <cstdio> #include <iostream> #include <cmath> using namespace std; typedef long long ll; const int N = 36000; int prime[N+5], tot; int MOD; bool mark[N+5]; void sss() { for(int i = 2;i <= N;i++) { if(!mark[i]) prime[++tot] = i; for(int j = 1; j <= tot; j++) { if(i * prime[j] > N) break; mark[i * prime[j]] = 1; if(i % prime[j] == 0) break; } } } int phi(int x) { int res = x; for(int i = 1;prime[i]*prime[i] <= x;i++) { if(x % prime[i] == 0){ res = res - res / prime[i]; while(x % prime[i] == 0) x /= prime[i]; } } if(x > 1) res = res - res / x; return res % MOD; } int n; int ksm(int a,int b) { int ans = 1; a %= MOD; while(b) { if(b & 1) ans = ans * a % MOD; a = a * a % MOD; b >>= 1; } return ans; } void solve() { int ans = 0; for(int i = 1;i*i <= n;i++) { if(n % i == 0) { ans = (ans + phi(i) * ksm(n,n/i-1)) % MOD; if(n / i != i) ans = (ans + phi(n/i) * ksm(n,i-1)) % MOD; } } printf("%d\n", ans); } int main() { sss(); int _;scanf("%d",&_); while(_--) { scanf("%d%d", &n, &MOD); solve(); } }
UVA10601
题意：给定12根长度相等的木棒的颜色（不超过６种颜色），求在翻转相等视为同一种的情况下，能拼成多少种不同的立方体
思路：首先分析立方体的置换
１．以相对面的中心旋转，90°，270°(4,4,4)，共３×２种，180°(2,2,2,2,2,2) 共３种
２．以对棱中心旋转，180°（1,1,2,2,2,2,2) 共６种
３．以对角旋转120°，240°（3,3,3,3) 共４×２种
４．不旋转（1,1,1,1,1,1,1,1,1,1,1,1) 共１种
综上，一共２４种置换方案，对于每一种置换，计数时做一次多维背包即可
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll dp[2][13][13][13][13][13][13]; int s[7],a[8],n; ll jc[13]; ll DP() { memset(dp,0,sizeof(dp)); dp[0][0][0][0][0][0][0] = 1; int o = 0; for(int i = 1; i <= n; i++) { for(int s1 = 0;s1 <=s[1];s1++) for(int s2 = 0;s2 <=s[2];s2++) for(int s3 = 0;s3 <=s[3];s3++) for(int s4 = 0;s4 <=s[4];s4++) for(int s5 = 0;s5 <=s[5];s5++) for(int s6 = 0;s6 <=s[6];s6++){ if(s1 + a[i] <= s[1]) dp[o^1][s1+a[i]][s2][s3][s4][s5][s6] += dp[o][s1][s2][s3][s4][s5][s6]; if(s2 + a[i] <= s[2]) dp[o^1][s1][s2+a[i]][s3][s4][s5][s6] += dp[o][s1][s2][s3][s4][s5][s6]; if(s3 + a[i] <= s[3]) dp[o^1][s1][s2][s3+a[i]][s4][s5][s6] += dp[o][s1][s2][s3][s4][s5][s6]; if(s4 + a[i] <= s[4]) dp[o^1][s1][s2][s3][s4+a[i]][s5][s6] += dp[o][s1][s2][s3][s4][s5][s6]; if(s5 + a[i] <= s[5]) dp[o^1][s1][s2][s3][s4][s5+a[i]][s6] += dp[o][s1][s2][s3][s4][s5][s6]; if(s6 + a[i] <= s[6]) dp[o^1][s1][s2][s3][s4][s5][s6+a[i]] += dp[o][s1][s2][s3][s4][s5][s6]; } o ^= 1; } return dp[o][s[1]][s[2]][s[3]][s[4]][s[5]][s[6]]; } int main() { int _;scanf("%d",&_); while (_--) { memset(s, 0, sizeof(s)); int x; jc[0] = 1; for (int i = 1;i <= 12;i++) { scanf("%d", &x); s[x]++; jc[i] = jc[i-1] * i; } ll ans = 0; n = 3;a[1] = a[2] = a[3] = 4; ans += ( DP() * 6 ); n = 6;for(int i = 1;i<=n;i++) a[i] = 2; ans += ( DP() * 3); n = 4;a[1] = a[2] = a[3] = a[4] = 3; ans += ( DP() * 8 ); n = 7;a[1] = a[2] = 1;a[3] = a[4] = a[5] = a[6] = a[7] = 2; ans += ( DP() * 6 ); ll ans2 = jc[12]; for(int i = 1;i<=6;i++) ans2 /= jc[s[i]]; ans += ans2; ans /= 24; printf("%lld\n",ans); } }
XDOJ 1228
题意：用１×２的矩阵拼成宽度为２，周长为ｎ的手环，靠近手和远离手视作不同，旋转后重合视为同一种方案，问有多少种方案
思路：polya套一个棋盘覆盖的DP，在宽度为２的情况下是一个斐波那契数列，用矩阵快速幂加速，头尾相接的方案数量等于矩阵的迹，这题可以推广宽度为ｍ的情况
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MOD = 1e9+7; int prime[36005],tot; bool mark[36005]; void sss() { for(int i = 2;i<=36000;i++) { if(!mark[i]) prime[++tot] = i; for(int j = 1;j <= tot && i*prime[j] <= 36000; j++) { mark[i * prime[j]] = 1; if(i % prime[j] == 0) break; } } } int phi(int x) { int res = x; for(int i = 1;prime[i] * prime[i] <= x;i++) { if(x % prime[i] == 0) { res = res - res / prime[i]; while(x % prime[i] == 0) x/=prime[i]; } } if(x > 1) res = res - res / x; return res % MOD; } ll ksm (ll a,int b) { ll res = 1; while(b) { if(b & 1) res = res * a % MOD; a = a * a % MOD; b >>=1; } return res; } struct JZ{ ll a[2][2]; JZ operator * (const JZ &o) const { JZ res; for(int i = 0;i<=1;i++) { for(int j = 0;j<=1;j++) { ll tmp = 0; for(int k = 0;k<=1;k++) tmp = (tmp + a[i][k] * o.a[k][j])%MOD; res.a[i][j] = tmp; } } return res; } void init(int x) { if(x == 1){ a[0][0] = a[0][1] = a[1][0] = 1; a[1][1] = 0; return ; } a[0][0] = a[1][1] = 1; a[0][1] = a[1][0] = 0; } }A,res; pair<int,int> fib(int n) { A.init(1); res.init(0); while(n) { if(n & 1) res = res * A; A = A * A; n >>= 1; } return make_pair(res.a[0][0],res.a[1][1]); } ll dp(int n) { if(n == 1 || n == 0) return 1; if(n == 2) return 3; pair<int,int> f = fib(n); return (f.first + f.second) % MOD; } int n; void solve() { ll ans = 0; for(int i = 1;i*i <= n;i++) { if(n % i == 0) { ans = (ans + phi(i)*1LL*dp(n/i))%MOD; if(n/i != i) ans = (ans + phi(n/i)*1LL*dp(i))%MOD; } } ans = ans * ksm(n,MOD-2) % MOD; if(n % 2 == 0) ans = (ans+1LL) % MOD; printf("%lld\n",ans); } int main() { sss(); while(scanf ("%d",&n)!=EOF) { solve(); } }
容斥计数
UVA11806
题意：在一个ｍ行ｎ列的矩形网格里放ｋ个相同的石子，问有多少种方法，每个格子最多放一个石子，所有石子要用完，并且第一行，第一列，最后一行，最后一列都得有石子
思路：容斥搞，四种情况的并集
#include <bits/stdc++.h> using namespace std; const int MOD = 1e6+7; typedef long long ll; ll c[405][505]; int m,n,k; void ycl(){ c[1][0] = c[1][1] = 1ll; for(int i=2;i<=400;i++) { c[i][0] = 1;c[i][i] = 1ll; for(int j = 1;j<i;j++) c[i][j] = (c[i-1][j-1] + c[i-1][j]) % MOD; } } int main() { ycl(); int _,ca=0;scanf("%d",&_); while(_--) { printf("Case %d: ",++ca); scanf("%d%d%d",&m,&n,&k); int ans = 0; for(int i = 0;i<(1<<4);i++) { int x = i,o = 1; int mm=m,nn=n; if(x&1)nn--,o=-o; x>>=1; if(x&1)mm--,o=-o; x>>=1; if(x&1)nn--,o=-o; x>>=1; if(x&1)mm--,o=-o; x>>=1; ans = ((ans + o*c[nn*mm][k])%MOD+MOD)%MOD; } if(k) printf("%d\n",ans); else puts("0"); } }
京公网安备 11010502036488号