HDU 4475 Downward paths (推公式)

这是题目的链接

http://acm.hdu.edu.cn/showproblem.php?pid=4475

题意：题目的意思就是说给出一个三角形，让你统计从第一层走到到最底层有多少条不同的路径。

题解：可以自己先推出第三个，然后通过观察得出规律：a[i]=a[i-1]*2*i(也可以写成a[i]=2^i*i)

注意题目给的数据比较大，有10^18,虽然对1000003取余，数据还是会很大，但是自己通过观察发现，i>=1000003的i%1000003取余为0，因为a[i]=a[i-1]*i*2，有一个阶乘包含了在里面。

 1  #include<stdio.h>
 2  #include<string.h>
 3  #include<stdlib.h>
 4  using namespace std;
 5  __int64 a[1000010];
 6  int main()
 7  {
 8     　　int T;
 9     　　scanf("%d",&T);
10      　  memset(a,0,sizeof(a));
11  　　   a[1]=2;
12  　　   for(int i=2;i<=1000003;i++)
13  　　   a[i]=(a[i-1]*2*i)%1000003;
14  　　   while(T--)
15 　　    {
16  　　　　__int64 n;
17  　　　　scanf("%I64d",&n);
18  　　　　if(n<1000003)
19  　　　　　　printf("%I64d
",a[n]);
20 　　　　else
21  　　　　printf("0
");
22 　　    }
23  　　   return 0;
24 }

View Code

如果把for循环放到while里面会TLE，因为每次循环的时候都会运行一遍，所以会超时。