AGC005D ~K Perm Counting

 ~K Perm Counting

神仙题++

转二分图+容斥比较好想

主要是最后的合并统计怎么做方便比较有趣

ptx大爷的博客 戳我

把二分图拆成链的想法很好

mark一下qwq

注意容斥的时候转longlong= =

#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define inf 20021225 #define ll long long #define mxn 2100 #define wph 924844033 using namespace std;int f[mxn<<1][mxn<<1][2]; int n,fac[mxn<<1],k; int a[mxn<<1],cnt; bool cant[mxn<<1]; int main() {int ff,ans,tmp;scanf("%d%d",&n,&k);fac[0]=1;for(int i=1;i<=(n<<1);i++) fac[i] = (ll)fac[i-1]*i%wph;for(int i=1;i<=k;i++)for(int j=0;j<=1;j++)for(int l=i;l<=n;l+=k){++cnt;if(l==i) cant[cnt]=1;}f[0][0][0]=1;for(int i=1;i<=cnt;i++)for(int j=0;j<=i;j++){f[i][j][0]=(f[i-1][j][0]+f[i-1][j][1])%wph;if(!cant[i]) f[i][j][1]=f[i-1][j-1][0];}ans=0;for(int i=0;i<=n;i++){ff=i&1?-1:1;tmp=((ll)f[cnt][i][0]+f[cnt][i][1])%wph*fac[n-i]%wph;ans=((ll)ans+ff*tmp+wph)%wph;}printf("%d\n",ans);return 0; }

 

转载于:https://www.cnblogs.com/hanyuweining/p/10321887.html

总结

以上是生活随笔为你收集整理的AGC005D ~K Perm Counting的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。