外国s网站建设,深圳市住建设局网站首页,WordPress推送到微信,设计个人网站容斥原理。
求出f(m) #xff0c;f(m)指代至少有m个位置不合法的方案数。
怎么求#xff1f;
注意到位置为id#xff0c;权值为v ,不合法的情况#xff0c;当且仅当 v idk或 v id-k
因此#xff0c;我们把每一个位置和权值抽象成点 #xff0c;不合法的情况之间连一…容斥原理。
求出f(m) f(m)指代至少有m个位置不合法的方案数。
怎么求
注意到位置为id权值为v ,不合法的情况当且仅当 v idk或 v id-k
因此我们把每一个位置和权值抽象成点 不合法的情况之间连一条边可以构成二分图。
借用大佬的图。 由此可知当选了n条边就恰好n个位置不合法限制条件是连的边不能相邻
把二分图展开成k条链进行dp。
还是借用大佬ez_lcw的图 由此总共有2n 个点 k 条链链与链之间无边 互不干涉。
dp(i,j,pd)表示考虑到第i号点 连了j条边是否有连接i 到 i-1号点。
转移方程 则可得
简单的乘法原理罢了。 #includebits/stdc.h
using namespace std;
long long n,k;
long long fac[4010];
long long dp[4010][4010][2];
int mod 1e97;
int pd[4999];//判断是否为链头 0 表示是头 头不能连接上一个
int main(){freopen(neverk.in,r,stdin);freopen(neverk.out,w,stdout);cinnk;fac[0] 1;for(int i 1;i n;i){fac[i] (fac[i-1]*(long long)i)%mod;}int tot 0;for(int i1;ik;i){for(int t0;t2;t){for(int ji;jn;jk){tot;if(i!j) pd[tot]1;}}}dp[0][0][0] 1;for(int i 1;i 2*n;i){for(int j 0;j n;j){dp[i][j][0] (dp[i-1][j][0] dp[i-1][j][1])%mod;if(jpd[i]) dp[i][j][1] dp[i-1][j-1][0];}}long long cnt 0;for(int i 0;i n;i){//coutfac[n-i] dp[2*n][i][0]dp[2*n][i][1]endl;long long t fac[n-i]*(dp[2*n][i][0]dp[2*n][i][1]);t%mod;//couttendl;if(i%2 0){cnt (cnt t)%mod;}else{cnt (cnt - t mod)%mod;}}coutcnt;return 0;
}
