提交记录 9628


用户 题目 状态 得分 用时 内存 语言 代码长度
lzoilxy noip18e. 【NOIP2018】填数游戏 Accepted 100 667.19 us 148 KB C++ 927 B
提交时间 评测时间
2019-06-20 22:23:19 2020-08-01 01:41:45
#include<algorithm>
#include<cstdio>
#define F dp[i+1][p][l]
using namespace std;
const int mod=1e9+7;
int n,m,s,x,y,mn,mx,num,ans,dp[10][550][10];
int pow(int k,int i)
{
	int t=1;
	while(i)
	{
		if(i&1) t=1ll*t*k%mod;
		k=1ll*k*k%mod;i>>=1;
	}
	return t;
}
int main()
{
	scanf("%d%d",&n,&m);
	if(n>m) swap(n,m);
	mn=min(n+1,m);s=(1<<n-1)-1;
	for(int i=0;i<(1<<n);++i) dp[1][i][0]=1;
	for(int i=1;i<mn;++i)
		for(int j=0;j<(1<<n);++j)
			for(int k=0;k<n;++k)
				if(dp[i][j][k])
					for(int p=0,l;p<(1<<n);++p)
					{
						if(((j>>1)&p)!=(p&s)) continue;
						if(k&&((j>>n-k+1)!=((p>>n-k)&((1<<k-1)-1)))) continue;
						l=n-1;
						for(;l>k;--l)
							if(((j>>n-l)&1)==((p>>n-l-1)&1))
								break;
						F+=dp[i][j][k];
						if(F>=mod) F-=mod;
					}
	for(int i=0;i<(1<<n);++i)
		for(int j=0;j<n;++j)
		{
			ans+=dp[mn][i][j];
			if(ans>=mod) ans-=mod;
		}
	printf("%d\n",1ll*ans*pow(3-(n==1),m-mn)%mod);
	return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #19.44 us28 KBAcceptedScore: 5

Testcase #213.04 us28 KBAcceptedScore: 5

Testcase #313.91 us32 KBAcceptedScore: 5

Testcase #412.22 us36 KBAcceptedScore: 5

Testcase #510.49 us32 KBAcceptedScore: 5

Testcase #69.67 us32 KBAcceptedScore: 5

Testcase #79.82 us32 KBAcceptedScore: 5

Testcase #89.76 us32 KBAcceptedScore: 5

Testcase #910.78 us32 KBAcceptedScore: 5

Testcase #109.3 us32 KBAcceptedScore: 5

Testcase #1111.63 us40 KBAcceptedScore: 5

Testcase #1211.92 us40 KBAcceptedScore: 5

Testcase #1310.91 us40 KBAcceptedScore: 5

Testcase #1472.77 us68 KBAcceptedScore: 5

Testcase #15189.83 us84 KBAcceptedScore: 5

Testcase #16582.16 us132 KBAcceptedScore: 5

Testcase #17663.52 us148 KBAcceptedScore: 5

Testcase #18667.19 us148 KBAcceptedScore: 5

Testcase #19663.73 us148 KBAcceptedScore: 5

Testcase #20665.52 us148 KBAcceptedScore: 5


Judge Duck Online | 评测鸭在线
Server Time: 2020-10-31 12:36:54 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用