网站设计制作合同,建设流网站项目,百度推广登录平台官网,wordpress神马优化ABC310D Peaceful Teams
洛谷[ABC310D] Peaceful Teams
题目大意
有 n n n个运动员以及 m m m对数#xff0c;每对数为 A i A_i Ai和 B i B_i Bi#xff0c;表示 A i A_i Ai和 B i B_i Bi不能分在同一小组。你需要将这些人分为 t t t个小组#xff0c;每个小组不…ABC310D Peaceful Teams
洛谷[ABC310D] Peaceful Teams
题目大意
有 n n n个运动员以及 m m m对数每对数为 A i A_i Ai和 B i B_i Bi表示 A i A_i Ai和 B i B_i Bi不能分在同一小组。你需要将这些人分为 t t t个小组每个小组不能为空。
求分组的方案数。当一个划分中有两个运动员属于同一个队伍而在另一个划分中属于不同的队伍时这两个划分是不同的。 1 ≤ n ≤ 10 , 0 ≤ m ≤ n ( n − 1 ) 2 1\leq n\leq 10,0\leq m\leq \dfrac{n(n-1)}{2} 1≤n≤10,0≤m≤2n(n−1) 题解
用状压DP。
设 f i , s f_{i,s} fi,s表示当前已经选择的运动员的状态为 s s s这些运动员分成了 i i i组。则转移式为 f i , s ∑ f i − 1 , s ⊕ j f_{i,s}\sum f_{i-1,s\oplus j} fi,s∑fi−1,s⊕j
其中 j j j满足 j s j j\ sj jsj且 j j j中状态为 1 1 1的运动员中不存在两个不能分在同一个小组的运动员。 j j j是否满足后面的条件可以 O ( m 2 n ) O(m2^n) O(m2n)预处理出而因为 s s s包含于 2 n − 1 2^n-1 2n−1 j j j包含于 s s s所以枚举 s s s和 j j j的次数为 3 n 3^n 3n每个运动员只有三种情况不在 s s s中、在 s s s中但不在 j j j中在 s s s中也在 j j j中。
注意当每个小组成员不变的情况下会将一种情况计算 t ! t! t!次所以答案为 f t , 2 n − 1 t ! \dfrac{f_{t,2^n-1}}{t!} t!ft,2n−1。
时间复杂度为 O ( m 2 n t 3 n ) O(m2^nt3^n) O(m2nt3n)。
code
#includebits/stdc.h
using namespace std;
int n,t,m,a[105],b[105],z[2005];
long long ans,f[15][2005];
int main()
{scanf(%d%d%d,n,t,m);for(int i1;im;i){scanf(%d%d,a[i],b[i]);}for(int s0;s1n;s){z[s]1;for(int k1;km;k){if((s(1a[k]-1))(s(1b[k]-1))){z[s]0;break;}}}f[0][0]1;for(int i1;it;i){for(int s1;s1n;s){for(int js;j1;j(j-1)s){if(z[j]) f[i][s]f[i-1][s^j];}}}ansf[t][(1n)-1];for(int i1;it;i) ans/i;printf(%lld,ans);return 0;
}
