题目
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。
输出包括一行表示合法的排列数。
解题思路
f i , j f_{i,j} fi,j 表示 i i i表示状态, j j j表示违背了的条件个数。
我们可以枚举队头,算出插入队头前的状态 l a s t last last和将插入队头后会违背的条件个数 f l a g flag flag(即判断状态里有多少个一)。
可以这么处理:
int find(int x){int xx=0; while (x) x-=(x&-x),xx++; return xx;}
动态转移方程为: f i , j + = f l a s t , j − f l a g f_{i,j}+=f_{last,j-flag} fi,j+=flast,j−flag
代码
#include<cstdio>
#include<algorithm>
#define rep(i,x,y) for (register int i=x;i<=y;i++)
#define fre(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout)
#define N 21
using namespace std;
const int pe=1e9+7;
int n,m,k,f[1<<N][N],ans,a[N],cnt,last,flag;
int find(int x){int xx=0; while (x) x-=(x&-x),xx++; return xx;}
int main(){//fre(count);scanf("%d%d%d",&n,&m,&k); int x,y; cnt=1<<n; f[0][0]=1; rep(i,1,m) scanf("%d%d",&x,&y),a[y-1]|=1<<(x-1); rep(i,0,cnt-1) rep(j,0,n-1) if ((i>j)&1){flag=find((last=(i^(1<<j)))&a[j]); rep(q,flag,k) (f[i][q]+=f[last][q-flag])%=pe; } rep(i,0,k) (ans+=f[cnt-1][i])%=pe; printf("%d",ans);
}