锐客网

  1. 首页 > it技术 > >

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<0dp[i?a[k]?1][msk|1< 这里有一个东西： MSK 这个状态在表达式中只提供了一个 1 的个数，这个时候把 MSK 直接定义成最终有多少个数字超过了限制，最后一维设成 j ：

dp[i][msk][j]=dp[i?1][msk][j]?(5?j+cnt[msk])+∑(msk$1<0dp[i?a[k]?1][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<

    推荐阅读


    上一篇：Codeforces Round #585 (Div. 2) F. Radio Stations

    下一篇：HDU-5628-Clarke-and-math-狄利克雷卷积