去年校赛题。。学到了新姿势orz。。 由于nm=40，所以min{n,m}=6，然后考虑6*6的情况就可以了。。 首先是状态的设计，如果保存上2行的状态这个状态数就是4^12，比较爆炸。。 如果用一个
去年校赛题。。学到了新姿势orz。。
由于nm<=40，所以min{n,m}<=6，然后考虑6*6的情况就可以了。。
首先是状态的设计，如果保存上2行的状态这个状态数就是4^12，比较爆炸。。
如果用一个位来标记当前位是否为连续的染色，这样状态数就可以降为8^6。。
比较巧妙的还是在转移，如果状压上一行再枚举下一行的状态是会T的。。
可是这题可以利用插头DP的思想(其实并不会插头DP)，逐点枚举转移，这样可以省去枚举当前行的代价。。
然后复杂度降到了O(nmk*8^6)。。
/**
* ┏┓ ┏┓
* ┏┛┗━━━━━━━┛┗━━━┓
* ┃ ┃
* ┃ ━ ┃
* ┃ ＞ ＜ ┃
* ┃ ┃
* ┃... ⌒ ... ┃
* ┃ ┃
* ┗━┓ ┏━┛
* ┃ ┃ Code is far away from bug with the animal protecting
* ┃ ┃ 神兽保佑,代码无bug
* ┃ ┃
* ┃ ┃
* ┃ ┃
* ┃ ┃
* ┃ ┗━━━┓
* ┃ ┣┓
* ┃ ┏┛
* ┗┓┓┏━━━━━━━━┳┓┏┛
* ┃┫┫ ┃┫┫
* ┗┻┛ ┗┻┛
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,l,r) for(int i=l;i>=r;i--)
#define link(x) for(edge *j=h[x];j;j=j->next)
#define mem(a) memset(a,0,sizeof(a))
#define ll unsigned long long
#define eps 1e-12
#define succ(x) (1<<x)
#define lowbit(x) (x&(-x))
#define sqr(x) ((x)*(x))
#define NM 10005
#define nm 300005
#define pi 3.1415926535897931
const ll inf=1000000007;
const ll mod=1e15+7;
using namespace std;
ll read(){
ll x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return f*x;
}
int n,m,p,_t,tot;
int d[2][nm],ans;
int main(){
while(~scanf("%d%d%d",&n,&m,&p)){
mem(d);
ans=0;
if(n>m)swap(n,m);
tot=succ(3*n)-1;p--;
_t=0;mem(d);
d[_t][0]=1;
inc(i,1,m){
inc(j,1,n){
_t^=1;mem(d[_t]);
inc(k,0,tot)if(d[_t^1][k]){
inc(v,0,p){
int t=k>>(3*(j-1));
if(i>1 && (t&3)==v && (t&4) )continue;
if(j>2 && ( (k>>(3*(j-2))) &3 )==v && ( (k>>(3*(j-3)))&3 )==v )continue;
int tmp=t>>3;
tmp<<=3;tmp|=v;
if(i>1 && (t&3)==v )tmp|=4;
tmp<<=3*(j-1);
tmp|=k^( t<<(3*(j-1)) );
d[_t][tmp]+=d[_t^1][k];
if(d[_t][tmp]>=inf)d[_t][tmp]-=inf;
}
}
}
}
inc(i,0,tot)ans+=d[_t][i],ans%=inf;
printf("%d\n",ans);
}
return 0;
}
1203: Happy to Eliminate
时间限制: 2 Sec 内存限制: 128 MB
提交: 43 解决: 14
[提交][状态][讨论版]
题目描述
输入
输出
样例输入
1 1 1 2 2 3 1 3 1 3 3 3
样例输出
1 81 0 9750
提示