FZU 2238 Daxia & Wzc's problem

公式。

$a×C_{m + i - 1}^m + d×C_{m + i - 1}^{m + 1}$。

推导过程可以看http://blog.csdn.net/queuelovestack/article/details/52260127

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<iostream>
using namespace std;
typedef long long LL;
const double pi=acos(-1.0),eps=1e-8;
void File()
{
    freopen("D:\in.txt","r",stdin);
    freopen("D:\out.txt","w",stdout);
}
template <class T>
inline void read(T &x)
{
    char c = getchar(); x = 0;while(!isdigit(c)) c = getchar();
    while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar();  }
}

LL a,d,i,m,p;

LL quick_mod(LL a, LL b)
{
    LL ans = 1;
    a %= p;
    while(b)
    {
        if(b & 1)
        {
            ans = ans * a % p;
            b--;
        }
        b >>= 1;
        a = a * a % p;
    }
    return ans;
}

LL C(LL n, LL m)
{
    if(m > n) return 0;
    LL ans = 1;
    for(int i=1; i<=m; i++)
    {
        LL a = (n + i - m) % p;
        LL b = i % p;
        ans = ans * (a * quick_mod(b, p-2) % p) % p;
    }
    return ans;
}

LL Lucas(LL n, LL m)
{
    if(m == 0) return 1;
    return C(n % p, m % p) * Lucas(n / p, m / p) % p;
}

int main()
{
    while(~scanf("%I64d%I64d%I64d%I64d", &a,&d,&m, &i))
    {
        p=1000000007;
        printf("%I64d
", (a*Lucas(m+i-1,m)+d*Lucas(m+i-1,m+1))%p);
    }
    return 0;
}