首页 > > 程序设计 > C/C++ >

bzoj2669 [ CQOI2012 ] -- DP+容斥

2018-06-17 23:18:28来源：未知阅读 ()

假设我们可以求出当a[1]..a[i]是局部最小值而其它点不加限制时的方案数，那么显然可以通过容斥求出答案。

那么怎么求当一些点是局部最小值时的方案数呢？

考虑DP。将数字从小到大放。令f[i][j]表示已经放了i个数，局部最小值的点的状态为j时的方案数，可得到方程：

f[i][j]=Σf[i-1][j]*cnt[j-(i-1)]+f[i-1][j^k](k&j>0)

其中cnt[j]表示当局部最小值的状态为j时能放数字的位置的个数与已放数字的局部最小值的个数之和。

显然cnt可以在每次DP前预处理出。

时间复杂度O(8*n*m*2⁸*容斥)

容斥的时间复杂度大约为10000

代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 #define M 12345678 
 6 int d[3]={-1,1,0};
 7 int X[9]={1,1,1,-1,-1,-1,0,0,0};
 8 int Y[9]={1,0,-1,1,0,-1,1,0,-1};
 9 int i,j,k,n,m,f[30][1<<8],Cnt[1<<8],Tot,K,c[10][10],p[10],Ans;
10 bool a[10][10],b[10][10];
11 char s[10];
12 inline int Calc(){
13     Tot=0;
14     for(int i=1;i<=n;i++)
15     for(int j=1;j<=m;j++)
16     if(a[i][j])c[i][j]=++Tot;else c[i][j]=0;
17     for(int s=0;s<p[Tot];s++){
18         Cnt[s]=0;
19         for(int i=1;i<=n;i++)
20         for(int j=1;j<=m;j++){
21             if(c[i][j]&&s&p[c[i][j]-1])Cnt[s]++;
22             if(!c[i][j]){
23                 int a1,a2;
24                 for(a1=0;a1<3;a1++){
25                     for(a2=0;a2<3;a2++)
26                     if(c[i+d[a1]][j+d[a2]]&&!(s&p[c[i+d[a1]][j+d[a2]]-1]))break;
27                     if(a2<3)break;
28                 }
29                 if(a1==3)Cnt[s]++;
30             }
31         }
32     }
33     memset(f,0,sizeof(f));
34     f[0][0]=1;
35     for(int i=1;i<=n*m;i++)
36     for(int k=0;k<p[Tot];k++){
37         f[i][k]=f[i-1][k]*(Cnt[k]-i+1)%M;
38         for(int j=0;j<Tot;j++)
39         if(p[j]&k)f[i][k]=(f[i][k]+f[i-1][k^p[j]])%M;
40     }
41     return f[n*m][p[Tot]-1];
42 }
43 inline void Dfs(int x,int y,int z){
44     if(x==n+1){
45         Dfs(1,y+1,z);
46         return;
47     }
48     if(y==m+1){
49         Ans=(Ans+(z&1?-1:1)*Calc())%M;
50         return;
51     }
52     Dfs(x+1,y,z);
53     for(i=0;i<3;i++){
54         for(j=0;j<3;j++)
55         if(a[x+d[i]][y+d[j]])break;
56         if(j<3)break;
57     }
58     if(i==3)a[x][y]=1,Dfs(x+1,y,z+1),a[x][y]=0;
59 }
60 int main()
61 {
62     for(p[0]=1,f[0][0]=1,i=1;i<=8;i++)p[i]=p[i-1]<<1;
63     scanf("%d%d",&n,&m);
64     for(i=1;i<=n;i++){
65         scanf("%s",s+1);
66         for(j=1;j<=m;j++)
67         if(s[j]=='X')a[i][j]=1;
68     }
69     Dfs(1,1,0);
70     printf("%d",(Ans+M)%M);
71     return 0;
72 }