前言

一道dp題

題目相關

題目鏈接

題目大意

一個$n?m$的棋盤（0,1,2）
并給出一個$2?c$的模板，求多少種棋盤包含模板
$q$次詢問
答案模$1e9+7$

數據范圍

$n\le 100,m\le 12,c\le 6,q\le 5$

題解

首先我們發現包含模板的數量不好算，但是我們發現可以求出不包含模板的數量$k$，這樣$ans=3^{n?m}?k$
考慮如何求$k$
我們發現$3^{12}=531441$，直接平方統計答案將會受不了，所以我們考慮不那么暴力的dp
我們發現有一種非常套路的dp方式，就是一個一個加，但我們算一下$max\{n?m?3^m\}$仍然過于大了，我們需要改變一下存狀態的方式
我們發現對于一個確定的模板，我們存狀態的時候不需要存那個位置的具體的值，我們只要存那一行它是否能成為右端點就好了，我們發現$max\{n?m?2^m\}=4915200$明顯可以接受
我們再考慮如何計算狀態和計算答案，我們只需要再開兩維做模板第一行、第二行分別的kmp的情況就好了，總復雜度為$\mathcal{O}(qnm{2}^{m?c}{c}^2)$
我們發現雖然說看起來復雜度很玄，但我們冷靜分析，發現上界是$\mathcal{O}(qnm{2}^m)$，隨便過

代碼

#include<cstdio> #include<cctype> #include<algorithm> #include<cstring> //#include<ctime> #define rg register typedef long long ll; template <typename T> inline T max(const T a,const T b){return a>b?a:b;} template <typename T> inline T min(const T a,const T b){return a<b?a:b;} template <typename T> inline void mind(T&a,const T b){a=a<b?a:b;} template <typename T> inline void maxd(T&a,const T b){a=a>b?a:b;} template <typename T> inline T abs(const T a){return a>0?a:-a;} template <typename T> inline void Swap(T&a,T&b){T c=a;a=b;b=c;} //template <typename T> inline void swap(T*a,T*b){T c=a;a=b;b=c;} template <typename T> inline T gcd(const T a,const T b){if(!b)return a;return gcd(b,a%b);} template <typename T> inline T lcm(const T a,const T b){return a/gcd(a,b)*b;} template <typename T> inline T square(const T x){return x*x;}; template <typename T> inline void read(T&x) {char cu=getchar();x=0;bool fla=0;while(!isdigit(cu)){if(cu=='-')fla=1;cu=getchar();}while(isdigit(cu))x=x*10+cu-'0',cu=getchar();if(fla)x=-x; } template <typename T> inline void printe(const T x) {if(x>=10)printe(x/10);putchar(x%10+'0'); } template <typename T> inline void print(const T x) {if(x<0)putchar('-'),printe(-x);else printe(x); } const ll mod=1000000007; ll pow(ll x,ll y) {ll res=1;for(;y;y>>=1,x=x*x%mod)if(y&1)res=res*x%mod;return res; } int n,m,c,q; int S; int f[2][4096][7][7]; void clean(int x) {for(rg int i=0;i<S;i++)for(rg int j=0;j<c;j++)for(rg int k=0;k<c;k++)f[x][i][j][k]=0; } ll ans; struct kmp {char b[7];int nxt[7];void KMP(){nxt[1]=0;int i,j=0;for(i=2;i<=c;i++){while(j&&b[i]!=b[j+1])j=nxt[j];if(b[i]==b[j+1])j++;nxt[i]=j;}}bool KMPING(char B,int&j){while(j&&B!=b[j+1])j=nxt[j];if(B==b[j+1])j++;if(j==c){j=nxt[j];return 1;}return 0;} }Q[2]; int main() {read(n),read(m),read(c),read(q); S=1<<(m-c+1);while(q--){ans=pow(3,n*m);scanf("%s %s",Q[0].b+1,Q[1].b+1);Q[0].KMP(),Q[1].KMP();int las=1,dq=0;clean(0);f[0][0][0][0]=1;for(rg int i=1;i<=n;i++)for(rg int j=1;j<=m;j++){dq^=1,las^=1;clean(dq);for(rg int k=0;k<S;k++)for(rg int a=0;a<c;a++)for(rg int b=0;b<c;b++){const ll v=f[las][k][a][b];if(!v)continue;{//0int J0=a,J1=b;if(j==1)J0=J1=0;bool r0=Q[0].KMPING('W',J0),r1=Q[1].KMPING('W',J1);int nk=k,na=a,nb=b;if(j<c||!((nk&(1<<(j-c)))&&r1)){if(nk&(1<<(j-c)))nk^=1<<(j-c);if(r0)nk^=1<<(j-c);na=J0,nb=J1;(f[dq][nk][na][nb]+=v)%=mod;}}{//1int J0=a,J1=b;if(j==1)J0=J1=0;bool r0=Q[0].KMPING('B',J0),r1=Q[1].KMPING('B',J1);int nk=k,na=a,nb=b;if(j<c||!((nk&(1<<(j-c)))&&r1)){if(nk&(1<<(j-c)))nk^=1<<(j-c);if(r0)nk^=1<<(j-c);na=J0,nb=J1;(f[dq][nk][na][nb]+=v)%=mod;}}{//2int J0=a,J1=b;if(j==1)J0=J1=0;bool r0=Q[0].KMPING('X',J0),r1=Q[1].KMPING('X',J1);int nk=k,na=a,nb=b;if(j<c||!((nk&(1<<(j-c)))&&r1)){if(nk&(1<<(j-c)))nk^=1<<(j-c);if(r0)nk^=1<<(j-c);na=J0,nb=J1;(f[dq][nk][na][nb]+=v)%=mod;}}}}for(rg int k=0;k<S;k++)for(rg int a=0;a<c;a++)for(rg int b=0;b<c;b++)ans=ans+mod-f[dq][k][a][b];print(ans%mod),putchar('\n');}return 0; }

總結

清新的dp題，練練手

總結

以上是生活随笔為你收集整理的[luogu3290][SCOI2016]围棋的全部內容，希望文章能夠幫你解決所遇到的問題。

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