2014
11-27

# 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要回溯