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

35

 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就行了

 //#pragma comment(linker, "/STACK:102400000, 102400000")

 #include <algorithm>

 #include <iostream>

 #include <cstdlib>

 #include <cstring>

 #include <cstdio>

 #include <vector>

 #include <cmath>

 #include <ctime>

 #include <list>

 #include <set>

 #include <map>

 using namespace std;

 typedef long long LL;

 typedef pair <int, int> P;

 const int N = 1e3 + ;

 LL mod = 1e9 + ;

 LL f[N];

 LL Pow(LL a , LL n , LL mod) {

     LL res = ;

     while(n) {

         if(n & )

             res = res * a % mod;

         a = a * a % mod;

         n >>= ;

     }

     return res;

 }

 LL Comb(LL a , LL b , LL mod) {

     if(a < b) {

         return ;

     }

     if(a == b) {

         return ;

     }

     LL ca = ;

     for(LL i =  ; i < b ; i++) {

         ca = (a - i) % mod * ca % mod;

     }

     return (ca * f[b]) % mod;

 }

 LL Lucas(LL n , LL m , LL mod) {

     LL ans = ;

     while(m && n && ans) {

         ans = (ans * Comb(n % mod , m % mod , mod)) % mod;

         n /= mod;

         m /= mod;

     }

     return ans;

 }

 int main()

 {

     f[] = ;

     for(LL j = ; j < N; ++j) {

         f[j] = j * f[j - ] % mod; //阶乘

     }

     for(LL j = ; j < N; ++j) {

         f[j] = Pow(f[j], mod - , mod); //逆元

     }

     LL a, b, m, i;

     while(cin >> a >> b >> m >> i) {

         if(i == ) {

             cout << a << endl;

             continue;

         }

         LL x = Lucas(m + i - , m, mod) * a % mod;

         LL y = Lucas(m +  + i - , m + , mod) * b % mod;

         cout << (x + y) % mod << endl;

     }

     return ;

 }