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.
草稿纸上手写一下
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 ;
}