长丰下塘新农村建设网站,梅西网页设计作业,江宁区住房建设局网站,中国企业500强公司排名全网唯一一篇容斥题解 Description Solution 看到这个题#xff0c;大部分人想的是状压dp 但是我是个蒟蒻没想到#xff0c;就用容斥切掉了。 并且复杂度比一般状压低#xff0c; #xff08;其实这个容斥的算法#xff0c;提出来源于ywy_c_asm#xff09; #xff08;然…全网唯一一篇容斥题解 Description Solution 看到这个题大部分人想的是状压dp 但是我是个蒟蒻没想到就用容斥切掉了。 并且复杂度比一般状压低 其实这个容斥的算法提出来源于ywy_c_asm 然而我知道了这个算法竟然和他写的不一样而且比他跑的快 进入正题 我们需要统计恰好满足匹配k个的情况。 那么我们可以先找出来恰好满足n个n-1n-2。。。k个的情况。 分别记为ans[i] ans[i]怎么算呢 先给出公式 ans[i]cal(i)-∑C(j,i)×ans[j] 其中i1jn cal(i)表示从n个中任意选择i个对于所有选择的情况的方案数的和。 cal(i)可以dfs暴力C(n,i)枚举每次统计答案。计入tot void dfs(int x,int has){if(xn1){if(has!up) return;ll lp1;for(int j1;jlen;j){las-1;for(int i1;iup;i){if(a[mem[i]][j]!?){if(las-1){lasa[mem[i]][j]-a;}else if(las!a[mem[i]][j]-a) return;}}if(las-1)lp(lp*26)%mod;}(totlp)%mod;return;}if(hasup) {mem[cnt]x;dfs(x1,has1);mem[cnt--]0;}if(n-xup-has) dfs(x1,has);
} 至于后面减去的部分。就是容斥的内容了。 大家可以自己画一个韦恩图理解一下。 这里有一个例子n4 现在我们要算ans[2],也就是恰好匹配2个的T的方案数 就是黄色的部分。 红色的数字是这个区域被算cal(i)的次数。 可见三个点的重复区域由于有C(3,2)种方法选到所以会被算C(3,2)次。 所以减去所有的ans[3]即可。 其他情况同理。 最后输出ans[1] 组合数打表。 理论复杂度O(n×len×2^15) Code #includebits/stdc.h
using namespace std;
typedef long long ll;
const int N20;
const int M52;
const int mod1000003;
char a[N][M];
int len;
int n,t,k;
int mem[N],cnt;
ll ans[N];
ll c[N][N];
ll sum;
ll tot;//tot measures
int up;//choose
int las;
void dfs(int x,int has){//dfs计算tot if(xn1){if(has!up) return;ll lp1;for(int j1;jlen;j){las-1;for(int i1;iup;i){if(a[mem[i]][j]!?){if(las-1){lasa[mem[i]][j]-a;}else if(las!a[mem[i]][j]-a) return;//两个字符不一样无合法方案 }}if(las-1)lp(lp*26)%mod;//如果都是‘’可以随便填否则只有一种 }(totlp)%mod;return;}if(hasup) {mem[cnt]x;dfs(x1,has1);mem[cnt--]0;}if(n-xup-has) dfs(x1,has);
}void clear(){memset(ans,0,sizeof ans);sum0;len0;
}
int main()
{for(int i0;iN-1;i){c[i][0]1;for(int j1;ji;j){c[i][j](c[i-1][j-1]c[i-1][j])%mod;}}scanf(%d,t);while(t--){clear();//清空数组其实没有必要 scanf(%d%d,n,k);for(int i1;in;i){scanf(%s,a[i]1);}lenstrlen(a[1]1);//长度 for(int in;ik;i--){//ans[i]计算 tot0;upi;dfs(1,0);sum0;for(int ji1;jn;j){//容斥的处理 (sumc[j][i]*ans[j])%mod;}ans[i](tot-summod)%mod;}printf(%lld\n,ans[k]);}return 0;
} 转载于:https://www.cnblogs.com/Miracevin/p/9585609.html
