1594:涂抹果酱 |
---|
时间限制: 1000 ms 内存限制: 524288 KB |
提交数: 669 通过数: 269 |
【题目描述】 |
Tyvj 两周年庆典要到了,Sam 想为 Tyvj 做一个大蛋糕。蛋糕俯视图是一个 N×M 的矩形,它被划分成 N×M 个边长为 1×1 的小正方形区域(可以把蛋糕当成 N 行 M 列的矩阵)。蛋糕很快做好了,但光秃秃的蛋糕肯定不好看!所以,Sam 要在蛋糕的上表面涂抹果酱。果酱有三种,分别是红果酱、绿果酱、蓝果酱,三种果酱的编号分别为 1,2,3。为了保证蛋糕的视觉效果,Admin 下达了死命令:相邻的区域严禁使用同种果酱。但 Sam 在接到这条命令之前,已经涂好了蛋糕第 KK 行的果酱,且无法修改。 |
现在 Sam 想知道:能令 Admin 满意的涂果酱方案有多少种。请输出方案数 mod106 。若不存在满足条件的方案,请输出 0。 |
【输入】 |
输入共三行。 |
第一行:N,M; |
第二行:K; |
第三行:M 个整数,表示第 K 行的方案。 |
字母的详细含义见题目描述,其他参见样例。 |
【输出】 |
输出仅一行,为可行的方案总数。 |
【输入样例】 |
2 2 |
1 |
2 3 |
【输出样例】 |
3 |
【提示】 |
样例说明: |
方案一 |
23 |
12 |
数据范围与提示: |
对于 30% 的数据,1≤N×M≤20; |
对于 60% 的数据,1≤N≤1000,1≤M≤3; |
对于 100% 的数据,1≤N≤10000,1≤M≤5。 |
思路:
其实也是一道板子题,不同的是相较于前两道题来说,这道题的状态应该使用三进制来存储(因为有三种果酱)。三进制的转移只需要开一个数组模拟三进制运算过程,其它的和二进制就基本上差不多啦(不要看下面我写的代码,又臭又长,还超时,[我也不知道是什么问题],其实最终代码非常短,只需要大概60行左右?)
代码:
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()//快读
{
char c=getchar();
ll x=0,f=1;
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}//不需要判负删掉来简化
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*f;
}
void write(int a)//快写
{
if(a<0) putchar('-'),a=-a;//不需要判负删掉来简化
if(a>=10)write(a/10);
putchar(a%10+48);
}
ll c[10200],f[10200][200],n,m;
ll a[10200];
ll k;ll num=0;
const int mod=1e6;
inline bool check(int x)
{
for(int i=m-1;i;i--)
{
if(x%c[i+1]/c[i]==x%c[i]/c[i-1]) return 0;
}
return 1;
}
inline bool check2(int x,int y)
{
for(int i=m-1;i>=0;i--)
{
if((x%c[i+1]/c[i])==(y%c[i+1]/c[i])) return 0;
}
return 1;
}
ll cnt=0;
inline void prepare()
{
for(int i=0;i<c[m];i++)
{
if(check(i)) a[++cnt]=i;
if(i==num) f[0][cnt]=1;//表示将第k行当做第0行去处理
}
}//所有状态都被预处理完成
inline void dp()
{
ll x=max(n-k,k-1);
ll y=min(n-k,k-1);
for(int i=1;i<=x;i++)
for(int j=1;j<=cnt;j++)
{
for(int l=1;l<=cnt;l++)
{
if(check2(a[l],a[j]))
{
f[i][j]=(f[i-1][l]+f[i][j])%mod;
}
}
}
ll ans1=0,ans2=0;
for(int i=1;i<=cnt;i++)
{
ans1+=f[x][i];
ans1%=mod;
ans2+=f[y][i];
ans2%=mod;
}
write(ans1*ans2%mod);
}
int main()
{
n=read();
m=read();
k=read();
c[0]=1;
for(int i=1;i<=m;i++)
{
int s;
s=read();
num=num*3+s-1;//将第k行的状态转化成三进制
c[i]=c[i-1]*3;
}
if(check(num)==0)
{
write(0);
return 0;
}
prepare();
dp();
return 0;
}
/*
算法流程:
1.判断k行是否有冲突
2.k行无冲突,预处理各行的状态
3.状态处理完成后进行dp,注意只需要dp一般,
方案数都是一样的
*/