首页 > ACM题库 > HDU-杭电 > HDU 3614-Card Game[解题报告]HOJ
2014
11-27

HDU 3614-Card Game[解题报告]HOJ

Card Game

问题描述 :


October 30, 2009.

After a night’s journey, finally we arrived at Wuhan University in the morning to participate the International Collegiate Programming Contest (ACM-ICPC).

……

Before went to sleep, my team mate Zhang and I played a popular card-game called "Builds up Train" to have a release. Although the game is a liite stupid, but it may have a lot of fun …

Assume there are 3 kinds of cards, and each of them has unlimited supply. If we take n cards out and arrange them in a row, we can get 3n differet rows. Now the problem is, how many different rows we can get using n cards and the number of cards of each kind is even?

输入:

The first line of input is a single integer T (1 ≤ T ≤ 1000), representing the number of test cases. Then T test cases follows. Each test case is described by a single integer in a single line: n (1 ≤ n ≤ 2147483647);

输出:

The first line of input is a single integer T (1 ≤ T ≤ 1000), representing the number of test cases. Then T test cases follows. Each test case is described by a single integer in a single line: n (1 ≤ n ≤ 2147483647);

样例输入:

3
1
2
2147483647

样例输出:

0 0 3 0
3 6 0 0
0 0 442 13482

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#define MAXN 11
#define MOD 40007

using namespace std;

const int n=8;

int a[MAXN][MAXN];

int x;

int DX[MAXN][MAXN]=
{
{0,1,1,0,1,0,0,0},
{1,0,0,1,0,1,0,0},
{1,0,0,1,0,0,1,0},
{0,1,1,0,0,0,0,1},
{1,0,0,0,0,1,1,0},
{0,1,0,0,1,0,0,1},
{0,0,1,0,1,0,0,1},
{0,0,0,1,0,1,1,0}
};

void print(int a[MAXN][MAXN])
{
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++) cout<<a[i][j]<<" ";
		cout<<endl;
	}
}

void mult(int x[MAXN][MAXN],int y[MAXN][MAXN],int z[MAXN][MAXN])
{
	int t[MAXN][MAXN];
	memset(t,0,sizeof(t));
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			for(int k=0;k<n;k++) t[i][k]=(t[i][k]+x[i][j]*y[j][k])%MOD;
	for(int i=0;i<n;i++)				
		for(int j=0;j<n;j++) z[i][j]=t[i][j];
}

void calc(int x[MAXN][MAXN],int y,int z[MAXN][MAXN])
{
	int t[MAXN][MAXN];
	int a[MAXN][MAXN];
	
	memset(a,0,sizeof(a));
	memset(t,0,sizeof(t));
	for(int i=0;i<n;i++) a[i][i]=1;
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++) t[i][j]=x[i][j];
	if(y%2==1)
		mult(a,t,a);
	y=y/2;
	while(y>0)
	{
		mult(t,t,t);
		if(y%2==1) mult(a,t,a);
		y=y/2;
	}
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++) z[i][j]=a[i][j];
}

void solve()
{
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++) a[i][j]=DX[i][j];
	//print(a);
	calc(a,x,a);
	//print(a);
	cout<<a[0][0]<<" "<<(a[3][0]+a[5][0]+a[6][0])%MOD<<" "<<(a[1][0]+a[2][0]+a[4][0])%MOD<<" "<<a[7][0]<<endl;
}

int main()
{
	int casen;
	scanf("%d",&casen);
	while(casen--)
	{
		cin>>x;
		solve();
	}
	return 0;
}

  1. if(j){
    int ans=a ;
    for(int x=j-1;x>=0;x–){
    if(!a ) break;
    ans=min(ans,a );
    sum+=ans;
    }
    }
    求解释,,dp的思路是什么呢?