做山西杂粮的网站,桂林北站到龙脊梯田,知识库管理系统软件,wordpress主题克隆解析
又是一道我不会的容斥题 qwq 本题的一个关键性质:答案有解时#xff0c;极小值不超过8个 所以可以对其进行状压
考虑从小到大填数 那么在极小值填完之前#xff0c;它的八连通必然是不能填的
设计dpi,sdp_{i,s}dpi,s表示从小到大填了i个数#xff0c;已经填完的极…解析
又是一道我不会的容斥题 qwq 本题的一个关键性质:答案有解时极小值不超过8个 所以可以对其进行状压
考虑从小到大填数 那么在极小值填完之前它的八连通必然是不能填的
设计dpi,sdp_{i,s}dpi,s表示从小到大填了i个数已经填完的极小值状态为s的方案数 不难作出转移
但是这样会统计一些不合法的方案 有的非极小值可能由于周围全是非极小值又随便填导致成为了极小值 所以要扣去所有非极小值成为极小值的方案
方法就是dfs枚举哪些非极小值成为极小值dp再按这些非极小值的个数的奇偶性进行容斥
代码
//暴力
#includebits/stdc.h
using namespace std;
const int mod12345678;
#define ll long long
#define il inline
il ll read(){ll x0,f1;char cgetchar();while(!isdigit(c)){if(c-)f-1;cgetchar();}while(isdigit(c)){xx*10c-0;cgetchar();}return x*f;
}
int n,m;
bool jd[20][20];
int a[20][20];
int dx[9]{0,0,-1,-1,-1,0,1,1,1},dy[9]{0,-1,-1,0,1,1,1,0,-1};
int ans;
inline bool exi(int x,int y){return x1xny1ym;
}
int x[50],y[50],tot,mi[50];
bool vis[12][12];
int dp[35][1050];
int num[1050];
int calc(){tot0;for(int i1;in;i){for(int j1;jm;j){if(jd[i][j]){tot;x[tot]i;y[tot]j;}}}for(int s0;smi[tot];s){memset(vis,0,sizeof(vis));num[s]n*m;for(int i1;itot;i){if(smi[i-1]) continue;int xxx[i],yyy[i];if(!vis[xx][yy]){vis[xx][yy]1;num[s]--;}for(int k1;k8;k){int nxxxdx[k],nyyydy[k];if(exi(nx,ny)vis[nx][ny]0){vis[nx][ny]1;num[s]--;}}}//printf(s%d num%d\n,s,num[s]);}memset(dp,0,sizeof(dp));dp[0][0]1;for(int i1;in*m;i){for(int s0;smi[tot];s){dp[i][s]1ll*dp[i-1][s]*max(num[s]-i1,0)%mod;if(dp[i][s]mod) dp[i][s]-mod;for(int k1;ktot;k){if((smi[k-1])0) continue;dp[i][s]dp[i-1][s-mi[k-1]];if(dp[i][s]mod) dp[i][s]-mod;}}}return dp[n*m][mi[tot]-1];
}
void dfs(int x,int y,int o){if(xn){/*for(int i1;in;i){for(int j1;jm;j) printf(%d ,jd[i][j]);putchar(\n);}*/if(o1){ans-calc();if(ans0) ansmod;}else{anscalc();if(ansmod) ans-mod;}//printf(ans%d\n\n,ans);return;}if(ym){dfs(x1,1,o);return;}dfs(x,y1,o);if(!jd[x][y]){for(int i1;i8;i){int nxxdx[i],nyydy[i];if(exi(nx,ny)jd[nx][ny]) return;}jd[x][y]1;dfs(x,y1,o1);jd[x][y]0;}
}
int main(){
#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);#endifmi[0]1;for(int i1;i28;i) mi[i]mi[i-1]1;nread();mread();char c;for(int i1;in;i){for(int j1;jm;j){scanf( %c,c);jd[i][j]cX;}}for(int i1;in;i){for(int j1;jm;j){if(!jd[i][j]) continue;for(int k1;k8;k){int nxidx[k],nyjdy[k];if(exi(nx,ny)jd[nx][ny]){printf(0);return 0;}}}}dfs(1,1,0);printf(%d\n,ans);
}
/**/
