5230. 【NOIP2017模拟A组模拟8.5】队伍统计
(File IO): input:count.in output:count.out Time Limits: 1500 ms Memory Limits: 524288 KB Detailed Limits
Description
现在有n个人要排成一列，编号为1->n 。但由于一些不明原因的关系，人与人之间可能存在一些矛盾关系，具体有m条矛盾关系(u,v),表示编号为u的人想要排在编号为v的人前面。要使得队伍和谐，最多不能违背k条矛盾关系（即不能有超过k条矛盾关系(u,v),满足最后v排在了u前面）。问有多少合法的排列。答案对10^9+7取模。
输入文件名为count.in。 第一行包括三个整数n,m,k。 接下来m行，每行两个整数u,v,描述一个矛盾关系(u,v)。 保证不存在两对矛盾关系(u,v),(x,y)，使得u=x且v=y 。
Output
输出文件名为count.out。 输出包括一行表示合法的排列数。
输入1： 4 2 1 1 3 4 2
输入2： 10 12 3 2 6 6 10 1 7 4 1 6 1 2 4 7 6 1 4 10 4 10 9 5 9 8 10
Sample Output
输出1： 18
输出2： 123120
Data Constraint
对于30%的数据，n<=10 对于60%的数据，n<=15 对应100%的数据，n,k<=20,m<=n*(n-1)，保证矛盾关系不重复。
题解
状压dp 用
f[s][i]
表示选人情况为
s
时，违反了i个矛盾关系 这样复杂度是
O(2nn2k)
，有点高
加个优化 因为矛盾关系不重复，用
a[i]
表示
log2(i)
的矛盾关系 这样就去掉了一个
n
最终复杂度是O(2nnk)
代码
#include<cstdio>
#include<cmath>
#define lowbit(a) ((a)&-(a))
#define mo 1000000007
#define N 30
long long f[
1<<
20][N];
long a[
1<<
20];
int main()
{
long n,m,l,x,y,s,i,j,k,q;
long long num;
freopen(
"count.in",
"r",stdin);
freopen(
"count.out",
"w",stdout);
scanf(
"%ld%ld%ld",&n,&m,&l);
for(i=
1;i<=m;i++){
scanf(
"%ld%ld",&x,&y);
a[
1<<(x-
1)]|=
1<<(y-
1);
}
f[
0][
0]=
1;
for(s=
0;s<(
1<<n);s++)
for(i=
0;i<=l;i++)
if(f[s][i])
for(q=s^((
1<<n)-
1);q;q^=lowbit(q)){
num=
0;
for(k=s&a[lowbit(q)];k;k^=lowbit(k))
num++;
if(i+num<=l)
f[s|lowbit(q)][i+num]+=f[s][i];
}
num=
0;
for(i=
0;i<=l;i++)
num=(num+f[(
1<<n)-
1][i])%mo;
printf(
"%lld\n",num%mo);
return 0;
}
