首页 > ACM题库 > HDU-杭电 > HDU 3610-Support Sichuan II[解题报告]HOJ
2014
11-27

HDU 3610-Support Sichuan II[解题报告]HOJ

Support Sichuan II

问题描述 :

Xiao Ming heard transported to the front to Dairy Milk. ABC would like, all meat not work. people in disaster areas also need to eat vegetables, so ABC has developed a super plant that can be used to eat. This plant from seed to germinate only 1 day time, and xth from the first day of germination, to yth days(including the yth day), every day they are breeding out of a seed, each plant will be the zth days in the germination of the harvest was sent to disaster.
0th day ABC only has a seed , ABC would like to know how many vegetables (not including seeds and which was send to disaster),in the nth day.

输入:

Multiple sets of data. Each test data row contains only four positive integers x, y, z, n, separated by spaces.
Where 0 <x <= y <z <= 20,0 <n <= 1000000000.

输出:

Multiple sets of data. Each test data row contains only four positive integers x, y, z, n, separated by spaces.
Where 0 <x <= y <z <= 20,0 <n <= 1000000000.

样例输入:

1 2 3 4

样例输出:

5

#include<stdio.h>
#define N 25 
#define md 1000000007
struct Matrix
{
	__int64 m[N][N];
}init;
int n,x,y,z;
Matrix Mult(Matrix m1,Matrix m2)
{
	Matrix ans;
	for(int i=1;i<=z;i++)
		for(int j=1;j<=z;j++)
		{
			ans.m[i][j]=0;
			for(int k=1;k<=z;k++)
				ans.m[i][j]=(ans.m[i][j]+m1.m[i][k]*m2.m[k][j])%md;
		}
	return ans;
}
Matrix Pow(Matrix m1,int b)
{
	Matrix ans;
	for(int i=1;i<=z;i++)
		for(int j=1;j<=z;j++)
			ans.m[i][j]=(i==j);
	while(b)
	{
		if(b&1)
		ans=Mult(ans,m1);
		m1=Mult(m1,m1);
		b>>=1;
	}
	return ans;
}
int main()
{
	int i,j;
	__int64 ans;
	while(scanf("%d%d%d%d",&x,&y,&z,&n)!=-1)
	{
		for(i=1;i<=z;i++)
		{
			for(j=1;j<=z;j++)
			init.m[i][j]=0;
		}
		for(i=x;i<=y;i++)
		{
			init.m[1][i]=1;
		}
		for(i=1;i<z;i++)
		{
			init.m[i+1][i]=1;
		}
		init=Pow(init,n-1);
		ans=0;
		for(i=1;i<z;i++)
			ans=(ans+init.m[i][1])%md;
		printf("%I64d\n",ans);
	}
	return 0;
}

  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. 可以参考算法导论中的时间戳。就是结束访问时间,最后结束的顶点肯定是入度为0的顶点,因为DFS要回溯