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)，保證矛盾關系不重復。

Solution

• 看到數據范圍，顯然就是狀壓DP了。

• 設 F[s][i] 表示已經選了的人的集合為 s 、已經違背了 i 條矛盾關系 的 合法排列數。

• 轉移時枚舉將要選的人，處理出會產生的矛盾關系即可。

• 那么如何快速處理出將會產生的矛盾關系呢？

• 考慮預處理出 a[x] 表示排在 x 以前會有矛盾的人的集合，

• 那么與 s & 的值二進制的 1 的個數就是所求的數量了。

• 時間復雜度為 O(2N?N?K) 。

Code

#include<cstdio> using namespace std; const int mo=1e9+7; int n,m,k,ans; int a[21],g[1<<20],p[21],f[1<<20][21]; inline int read() {int X=0,w=1; char ch=0;while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();return X*w; } inline void dfs(int x,int y,int z) {if(z>n) return;g[x]=y;dfs(x,y,z+1);dfs(x+p[z],y+1,z+1); } int main() {n=read(),m=read(),k=read();for(int i=p[0]=1;i<=n;i++) p[i]=p[i-1]<<1;dfs(0,0,0);for(int i=1;i<=m;i++){int x=read(),y=read();a[y]|=p[x-1];}f[0][0]=1;for(int s=0;s<p[n];s++)for(int j=1;j<=n;j++)if(p[j-1]&s){int sum=g[s&a[j]];for(int i=sum;i<=k;i++) f[s][i]=(f[s][i]+f[s-p[j-1]][i-sum])%mo;}for(int i=0;i<=k;i++) ans=(ans+f[p[n]-1][i])%mo;printf("%d",ans);return 0; }

總結

以上是生活随笔為你收集整理的JZOJ 5230. 【NOIP2017模拟A组模拟8.5】队伍统计的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。