传送门
Description:
1
// Q.cpp
2
3
using namespace std;
4
const long long M = 1000000007;
5
const long long MAXL = 1000000;
6
long long a[MAXL];
7
long long Q(int n, long long t)
8
{
9
if(n < 0) return t;
10
return (Q(n - 1, t) + Q(n - 1, (t * a[n]) % M)) % M;
11
}
12
int main()
13
{
14
int n;
15
while(cin >> n)
16
{
17
for(int i = 0; i < n; ++i)
18
{
19
cin >> a[i];
20
a[i] %= M;
21
}
22
cout << Q(n - 1, 1) << endl;
23
}
24
return 0;
25
}
Input:
Input consists of several test cases. Each test case begins with an integer n. Then it's followed by n integersa[i].
0<n<=1000000
0<=a[i]<=10000
There are 100 test cases at most. The size of input file is less than 48MB.
Output:
Maybe you can just copy and submit. Maybe not.
样例输入
1 233 1 666
样例输出
234 667
题目来源
2018 ACM-ICPC 中国大学生程序设计竞赛线上赛
比赛时看到这个代码，没想到递归转成递推，一直想着是不是有什么规律，，，道行太浅，继续修炼！
对了，不要用cin，cout,即使解除了iostream与stdio输出流的绑定，还是超时。
#include<iostream>
#include<cstdio>
using namespace std;
const long long M=1000000007;
const long long MAXL=1000000;
long long a;int main()
{int n;while(~scanf("%d",&n)){long long res=1;for(int i=0;i<n;i++){scanf("%lld",&a);res=(res+(res*a)%M)%M;}printf("%lld\n",res);}return 0;
}