2012 Multi-University Training Contest 1 Divide Chocolate

1120 단어 Training
상태 표시:
pp[i][0][j]: 앞 i행에 j부분이 있고 i행의 두 칸이 같은 부분에 속하는 방법수
pp[i][1][j]: 전 i행은 j부분이 있고 i행의 두 칸은 서로 다른 부분에 속하는 방법수
#include <stdio.h>
#include <string.h>
#define N 100000007 
int dp[1005][2][2005]; 
int n,k; 
void solve()
{
		int i,j;
		memset(dp,0,sizeof(dp));
		dp[1][0][1]=dp[1][1][2]=1;
		for(i=1;i<=n;i++)
			for(j=0;j<=k;j++) 
			{ 
				 dp[i+1][0][j]=(dp[i+1][0][j]+dp[i][0][j]+(dp[i][1][j])*2)%N;
		         dp[i+1][0][j+1]=(dp[i+1][0][j+1]+dp[i][0][j]+dp[i][1][j])%N;
		         dp[i+1][1][j]=(dp[i+1][1][j]+dp[i][1][j])%N;
		         dp[i+1][1][j+1]=(dp[i+1][1][j+1]+(dp[i][0][j]*2)+(dp[i][1][j]*2))%N;
		         dp[i+1][1][j+2]=(dp[i+1][1][j+2]+dp[i][0][j]+dp[i][1][j])%N;
			 }	
		
} 
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&k);
		solve();
		printf("%d
",(dp[n][1][k]+dp[n][0][k])%N); } }

좋은 웹페이지 즐겨찾기