"
题意：给出一个数列a【n】，规定一种操作：用其前n项和s【n】覆盖a【n】，一共操作k次，输出数列a。1<=n<=2000，0<=k<=109，0<=ai<=109。
思路：首选想到用矩阵快速幂做，而且针对大数k，我设计了一种方案：储存20~229（230略>109），把k化为2进制，按位&1，是1就加上相应的2^n，很方便有木有？！无奈其复杂度是O(n3)的，当n=200时就差不多TLE了；而且也很耗空间。
由此得出结论：当对数列进行不规则变换时，用矩阵做；当进行纯洁的变换时，还是找规律吧O__O""…
最后找到的规律为：Sn=sum(Xn-i * ai)，i=1<=n。Xn-i = C(k-1+n-i，k-1)。
1 // 2013-08-01 20:36:10
2 // 0KB 92ms 1060B
3 // by Siriuslzx
4 #include
5 #include [span style=""color: rgba(0, 0, 255, 1)"">string.h>
6 typedef long long LL;
7
8 const int N = 2005;
9 const int Mod = 1000000007;
10 LL a【N】,x【N】,iv【N】;
11
12 void gcd(LL a, LL b, //代码效果参考：https://v.youku.com/v_show/id_XNjQwNjg1NTY0NA==.html
LL&d, LL &x, LL &y){13 if(!b){d = a, x = 1, y = 0;}
14 else{
15 gcd(b, a%b, d, y, x);
16 y -= x*(a/b);
17 }
18 }
19 LL inv(LL a, LL n){
20 LL d, x, y;
21 gcd(a, n, d, x, y);
22 return d == 1 ? (x+n)%n : -1;
23 }
24 void init(int n, int k){
25 x【0】 = 1;
26 for(int i = 1; i < n; i++)
27 x【i】 = x【i-1】(k-1+i)%Modiv【i】%Mod;
28 }
29
30 int main(){
31 int n,k,i,j;
32 LL sum;
33 for(i = 1; i < N; i++)
34 iv【i】 = inv(i, Mod);
35 scanf(""%d%d"",&n,&k);
36 for(i = 1; i <= n; i++)
37 scanf(""%I64d"",&a【i】);
38 // 其实当k==0时依然兼容，只是再算感觉浪费
39 if(!k){
40 for(i = 1; i < n; i++)
41 printf(""%I64d "",a【i】);
42 printf(""%I64d\n"",a【n】);
43 return 0;
44 }
45 // 后来把//代码效果参考：https://v.youku.com/v_show/id_XNjQwMDQxMDExNg==.html
中间这段掐了再交，时间还是一样的46 init(n,k);
47 for(i = 1; i <= n; i++){
48 sum = 0;
49 for(j = 1; j <= i; j++)
50 sum = (sum + x【i-j】*a【j】%Mod)%Mod;
51 if(i != n)
52 printf(""%I64d "",sum);
53 else printf(""%I64d\n"",sum);
54 }
55 return 0;
56 }
通过做这题得到的一个结论：以1为首项的k阶等差数列，An = C(k+n-1，k)。
"
