FZU 8月有奖月赛A Daxia & Wzc's problem (Lucas)

Problem A Daxia & Wzc's problem

Accept: 42 Submit: 228
Time Limit: 1000 mSec Memory Limit : 32768 KB

Problem Description

Daxia在2016年5月期间去瑞士度蜜月,顺便拜访了Wzc,Wzc给他出了一个问题：

Wzc给Daxia等差数列A(0),告诉Daxia首项a和公差d;

首先让Daxia求出数列A(0)前n项和,得到新数列A(1);

然后让Daxia求出数列A(1)前n项和,得到新数列A(2);

接着让Daxia求出数列A(2)前n项和,得到新数列A(3);

...

最后让Daxia求出数列A(m-1)前n项和,得到新数列A(m);

Input

测试包含多组数据,每组一行,包含四个正整数a(0<=a<=100),d(0<d<=100),m(0<m<=1000),i(1<=i<=1000000000).

Output

每组数据输出一行整数,数列A(m)的第i项mod1000000007的值.

Sample Input

1 1 3 4

Sample Output

Hint

A(0): 1 2 3 4

A(1): 1 3 6 10

A(2): 1 4 10 20

A(3): 1 5 15 35

So the 4th of A(3) is 35.
Cached at 2016-08-17 19:08:15.

Submit Back Status

草稿纸上手写一下

a1 a1+d a1+2d a1+3d...

a1 2a1+d 3a1+3d 4a1+6d...

a1 3a1+d 6a1+4d 10a1+10d...

...

可以发现这个是一个类似杨辉三角的东西，大概就是C(n, m)这样算的。

然后就用Lucas就行了

 1 //#pragma comment(linker, "/STACK:102400000, 102400000")
 2 #include <algorithm>
 3 #include <iostream>
 4 #include <cstdlib>
 5 #include <cstring>
 6 #include <cstdio>
 7 #include <vector>
 8 #include <cmath>
 9 #include <ctime>
10 #include <list>
11 #include <set>
12 #include <map>
13 using namespace std;
14 typedef long long LL;
15 typedef pair <int, int> P;
16 const int N = 1e3 + 5;
17 LL mod = 1e9 + 7;
18 LL f[N];
19 
20 LL Pow(LL a , LL n , LL mod) {
21     LL res = 1;
22     while(n) {
23         if(n & 1)
24             res = res * a % mod;
25         a = a * a % mod;
26         n >>= 1;
27     }
28     return res;
29 }
30 
31 LL Comb(LL a , LL b , LL mod) {
32     if(a < b) {
33         return 0;
34     }
35     if(a == b) {
36         return 1;
37     }
38     LL ca = 1;
39     for(LL i = 0 ; i < b ; i++) {
40         ca = (a - i) % mod * ca % mod;
41     }
42     return (ca * f[b]) % mod;
43 }
44 
45 LL Lucas(LL n , LL m , LL mod) {
46     LL ans = 1;
47     while(m && n && ans) {
48         ans = (ans * Comb(n % mod , m % mod , mod)) % mod;
49         n /= mod;
50         m /= mod;
51     }
52     return ans;
53 }
54 
55 int main()
56 {
57     f[0] = 1;
58     for(LL j = 1; j < N; ++j) {
59         f[j] = j * f[j - 1] % mod; //阶乘
60     }
61     for(LL j = 0; j < N; ++j) {
62         f[j] = Pow(f[j], mod - 2, mod); //逆元
63     }
64     LL a, b, m, i;
65     while(cin >> a >> b >> m >> i) {
66         if(i == 1) {
67             cout << a << endl;
68             continue;
69         }
70         LL x = Lucas(m + i - 1, m, mod) * a % mod;
71         LL y = Lucas(m + 1 + i - 2, m + 1, mod) * b % mod;
72         cout << (x + y) % mod << endl;
73     }
74     return 0;
75 }

View Code