bzoj2669 [ CQOI2012 ] -- DP+容斥。本站提示廣大學習愛好者：（bzoj2669 [ CQOI2012 ] -- DP+容斥）文章只能為提供參考，不一定能成為您想要的結果。以下是bzoj2669 [ CQOI2012 ] -- DP+容斥正文
假設我們可以求出當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*28*容斥)
容斥的時間復雜度大約為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 }
bzoj2669
