mengbierr

一个蒟蒻的博客

6月25

AGC005 D – ~K Perm Counting

题意

求有多少长度为n的排列满足 |a_i-i|=k

题解

把问题视作二分图匹配,发现不合法边就是一些链,那么每条链做dp,f[i][j][0/1]表示在点i,选了j条边,下一个点选没选,定义i+1为转移的下一个点。
f[i+1][j][0]=f[i][j][0]+f[i][j][1];
f[i+1][j][1]=f[i][j][0];
然后定义g[i]表示选了至少i条不合法边的方案数。
g[i]=f[n][i][0]+f[n][i][1];
容斥一下即可。
最近大多数都在嘴巴ac,没写代码233.

发表评论

电子邮件地址不会被公开。 必填项已用*标注