HDU 5519 Kykneion asma（沈阳站K题&&DP+容斥）
这题想了好久没想出来，最后是学习的这里的做法解决的：K题题解
基于FFT，本弱到现在还是不会写，所以并不能提供FFT的写法。
分析：设 W(n,a0,a1,a2,a3,a4) 代表可以有前导 0 的 n 位 5 进制数字，至多 ai 个数字 i 的方案数。那么
ans=W(n?1,a0,a1?1,a2,a3,a4)+W(n?1,a0,a1,a2?1,a3,a4)+W(n?1,a0,a1,a2,a3?1,a4)+W(n?1,a0,a1,a2,a3,a4?1)
现在问题变成了如何求 W(n,a0,a1,a2,a3,a4)，这里用容斥来求：
设 V(n,a0,a1,a2,a3,a4)代表 n位 5进制的数字， 0,1,2,3,4中有数字超过规定限制的情况。
W(n,a0,a1,a2,a3,a4)=5n?V(n,a0,a1,a2,a3,a4)
设 S(ab1,ab2..,abm) 代表数 b1,b2,..,bm 一定超过限制的方案数。
V(n,a0,a1,a2,a3,a4)=∑iS(ai)?∑i,j,i,j互不相等S(ai,aj)+∑i,j,k,i,j,k互不相等S(ai,aj,ak)?∑i,j,k,l,i,j,k,l互不相等S(ai,aj,ak,al)+S(a0,a1,a2,a3,a4)
dp[i][msk][MSK] 代表最终有状态 MSK 的数一定超过限制，当前 i 个数，有 msk 个数超过限制，这里可以 msk 是 MSK 的子状态。
注意点：这里 MSK 中存在的数， msk 不存在的数，不能填入 i 位。
设 cnt[msk] 代表这个状态下 1 的个数
这样得到
dp[i][msk][MSK]=dp[i?1][msk][MSK]?(5?cnt[MSK]+cnt[msk])+∑(msk$1<
dp[i][msk][j]=dp[i?1][msk][j]?(5?j+cnt[msk])+∑(msk$1<
S(ab1,ab2..,abm)=∑cnt[msk]=jdp[n][msk][j]
此时复杂度为 o(4?n?25?52)
【HDU 5519 Kykneion asma（沈阳站K题&&DP+容斥）】附上代码：
#include
#include
#define LL long long
#define FOR(i,x,y)for(int i = x;
i < y;
++ i)
#define IFOR(i,x,y) for(int i = x;
i < y;
-- i)using namespace std;
typedef vector VT;
const int maxn = 15010;
const int maxm = 30030;
const int Mod = 1e9+7;
const int MSK = 1<<5;
int n,a[5];
void gcd(LL a,LL b,LL& d,LL& x,LL& y){
if(!b){d = a;
x = 1;
y = 0;
}
else{gcd(b,a%b,d,y,x);
y -= x*(a/b);
}
}LL Inv(LL a,LL n){
LL d,x,y;
gcd(a,n,d,x,y);
return d == 1 ? (x+n)%n : -1;
}LL fac[maxn],inv[maxn],cnt[MSK];
void init(){
fac[0] = 1;
inv[0] = 1;
FOR(i,1,maxn){
fac[i] = i*fac[i-1]%Mod;
LL p = Inv(i,Mod);
inv[i] = inv[i-1]*p%Mod;
}
FOR(i,0,MSK)cnt[i] = __builtin_popcount(i);
}LL dp[maxn][MSK];
LL Pow;
LL C(LL p,LL q){
return fac[p]*inv[q]%Mod*inv[p-q]%Mod;
}LL quickpow(LL a,LL n,LL m){
LL ans=1;
while(n){
if(n&1) ans = (ans*a)%m;
a = (a*a)%m;
n>>=1;
}
return ans;
}void work(){
LL ans = 0;
FOR(p,1,5){
if(!a[p])continue;
ans += Pow;
ans %= Mod;
-- a[p];
-- n;
FOR(j,1,6){
memset(dp,0,sizeof(dp));
dp[0][0] = 1;
FOR(i,1,n+1){
FOR(msk,0,MSK){
if(cnt[msk] <= j){
dp[i][msk] = dp[i-1][msk]*(5-j+cnt[msk])%Mod;
FOR(k,0,5){
if((msk & (1<
推荐阅读
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- 解题报告|51nod 1667 概率好题
- 树形dp|Codeforces 917D Stranger Trees 树形dp+容斥原理
- DP|[codeforces 917D]Stranger Trees
- 容斥原理|【WC2017模拟1.22】简单题
- 容斥原理（翻译）