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取模。

Input

输入文件名为count.in。
第一行包括三个整数n,m,k。
接下来m行，每行两个整数u,v,描述一个矛盾关系(u,v)。
保证不存在两对矛盾关系(u,v),(x,y)，使得u=x且v=y 。

Output

输出文件名为count.out。
输出包括一行表示合法的排列数。

Sample Input

输入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;
}

秒客网

JZOJ 5230. 【NOIP2017模拟A组模拟8.5】队伍统计