首页 > ACM题库 > HDU-杭电 > HDU 3941-Bear-Baby[解题报告]HOJ
2015
04-14

HDU 3941-Bear-Baby[解题报告]HOJ

Bear-Baby

问题描述 :

Bear-Baby is a smart boy and he likes playing games. One day he played a simple game with one guy. In this game there are N piles of stones, and each of these piles has K stones at first. When the game starts, two participants take turns to pick up stones following this rule: the one who should act now must choose two different piles (e.g. , pile i and j, i≠j ), and remove the same number of stones from these two piles. The one who cannot act loses the game. Now Bear-Baby wants to study the game. He’d like to figure out the Sprague-Grundy value of each situation that will appear during the game.
Given the number of the piles N and the size of each pile K, Bear-Baby wonders how many different situations could appear during the game. We consider that two situations are the same if they are same after reorder the piles, i.e situations (1,1,3) (1,3,1) and (3,1,1) are the same.

输入:

There is an integer T(T<=100) in the first line indicating the number of test cases.
  In each test case there are two numbers N and K (1<=N,K<=100) telling the number of piles and the size of each pile in one line.

输出:

There is an integer T(T<=100) in the first line indicating the number of test cases.
  In each test case there are two numbers N and K (1<=N,K<=100) telling the number of piles and the size of each pile in one line.

样例输入:

2
2 3
3 2

样例输出:

Case #1: 4
Case #2: 5

Hint
For the Case #2, from the initial situation (2,2,2), we can get five different situations (2,2,2) (1,1,2) (0,0,2) (0,1,1) (0,0,0)

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <cstring>
#include <string>
#include <map>
#include <set>
#include <vector>
using namespace std;

const int MOD=1000000007;
const int MaxN=103;
const int MaxM=203;
int N,K,f[2][MaxN][MaxM],s[MaxN][MaxM];


int solve()
{
 int MaxK=2*K+1;
 for (int i=0; i<=K; ++i)
 	for (int j=0; j<=MaxK; ++j) f[0][i][j]=s[i][j]=0;
 f[0][0][0]=1;
 s[0][0]=1;
 int cur=0,last;
 for (int i=1; i<=N; ++i)
 {
 last=cur;
 cur=1-cur;
 for (int j=0; j<=K; ++j)
 	for (int k=0; k<=MaxK; ++k) f[cur][j][k]=0;
 f[cur][0][0]=1;
 for (int j=1; j<=K; ++j)
 {
 	for (int k=j; k<MaxK-1; ++k)
 	{
 		f[cur][j][k]=f[cur][j-1][k-1]+f[last][j][k-j];
 		f[cur][j][k]%=MOD;
 	}
 	for (int p=0; p<=j; ++p)
 	{
 	 int cnt=MaxK-1-j;
 	 f[cur][j][MaxK-1]+=s[p][cnt];
 	 f[cur][j][MaxK-1]%=MOD;
 	 cnt=MaxK-j;
 	 f[cur][j][MaxK]+=s[p][cnt];
 	 f[cur][j][MaxK]%=MOD;
 	}
 }
 for (int j=0; j<=K; ++j)
 	for (int k=MaxK; k>=0; --k) s[j][k]=f[cur][j][k];
 for (int j=0; j<=K; ++j)
 	for (int k=MaxK-2; k>=0; --k)
 	{
 		s[j][k]+=s[j][k+2];
 		s[j][k]%=MOD;
			} 
	//	for (int j=0; j<=K; ++j)
	//		for (int k=0; k<=MaxK; ++k) cout<<i<<" "<<j<<" "<<k<<":"<<f[cur][j][k]<<endl;
 }
 int ans=0;
 for (int i=0; i<=K; ++i)
 	for (int j=i+i; j<MaxK; j+=2) 
 	{
 	// cout<<cur<<" "<<i<<" "<<j<<"---"<<f[cur][i][j]<<endl;
 	 ans+=f[cur][i][j];
 	 ans%=MOD;
 	}
 return ans;
}

int main()
{
 int Testnum;
 scanf("%d",&Testnum);
 for (int Test=1; Test<=Testnum; ++Test)
 {
 scanf("%d %d",&N,&K);
 printf("Case #%d: %d\n",Test,solve());
	}
}