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

Description

现在有n个人要排成一列，编号为1->n 。但由于一些不明原因的关系，人与人之间可能存在一些矛盾关系，具体有m条矛盾关系(u,v),表示编号为u的人想要排在编号为v的人前面。要使得队伍和谐，最多不能违背k条矛盾关系（即不能有超过k条矛盾关系(u,v),满足最后v排在了u前面）。问有多少合法的排列。答案对10^9+7取模

Data Constraint

对于30%的数据，n<=10 对于60%的数据，n<=15 对应100%的数据，n,k<=20,m<=n*(n-1)，保证矛盾关系不重复。

分析

这里的n很小，只有20，自然想到状态压缩。 设 fs,i 表示当前已经被安排进队伍里面的人的集合s，违背了i条矛盾关系。 转移比较简单，枚举当前加入队伍的人是谁。 用一个二进制状态 fi 表示不能排在第i个人前面的人是哪些。 将状态s& fi 之后，求出1的个数，就是当前加入队伍的人违背的矛盾关系数。 这样的时间复杂度是 O(2nn2k) 。 我们发现我们在求一个状态里面的01个数的时候比较浪费时间，那么就预处理一下。

code

#include <cstdio> #include <algorithm> #include <cstring> #include <string.h> #include <cmath> #include <math.h> #define N 23 #define ll long long #define mo 1000000007 using namespace std; int n,m,k,u,v,pre[1048580],z[N],g[N]; ll ans,f[1048580][N]; void dg(int x,int s,int y) { if(x==n) { pre[s]=y; return; } dg(x+1,s+z[x],y+1); dg(x+1,s,y); } int main() { freopen("count.in","r",stdin); freopen("count.out","w",stdout); scanf("%d%d%d",&n,&m,&k); z[0]=1; for(int i=1;i<=n;i++) z[i]=z[i-1]*2; for(int i=1;i<=m;i++) scanf("%d%d",&u,&v),g[u]+=z[v-1]; dg(0,0,0); f[0][0]=1; for(int s=0;s<z[n];s++) for(int i=1;i<=n;i++) { if((s&z[i-1])!=0)continue; for(int j=0;j+pre[s&g[i]]<=k;j++) { f[s+z[i-1]][j+pre[s&g[i]]]=(f[s+z[i-1]][j+pre[s&g[i]]]+f[s][j])%mo; } } for(int i=0;i<=k;i++) ans=(ans+f[z[n]-1][i])%mo; printf("%lld",ans); }