FZU Problem 2238 Daxia & Wzc's problem

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);

规律题，首先写出 a、a+d、a+2d、a+3d...这个容易写出

下面一行也容易写出：a、2a+d、3a+3d....

再下一行，确实难写，但是通过上面两行可以得出，dp[i][j] = dp[i-1][j] + dp[i][j-1]

然后可以顺利写出后面的，找到通项公式。

ans = C(m+i-1,m)*a + C(m+i-1,i-2)*d

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

#include <iostream>

#include <sstream>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <string>

LL a,d,m,i;

const int MOD = ;

LL quick_pow (LL a,LL b,LL MOD)

{

    //求解 a^b%MOD的值

    LL base=a%MOD;

    LL ans=; //相乘，所以这里是1

    while (b)

    {

        if (b&)

        {

            ans=(ans*base)%MOD; //如果这里是很大的数据，就要用quick_mul

        }

        base=(base*base)%MOD;    //notice

        //注意这里,每次的base是自己base倍

        b>>=;

    }

    return ans;

}

LL C (LL n,LL m,LL MOD)

{

    if (n<m) return ; //防止sb地在循环，在lucas的时候

    if (n==m) return ;

    LL ans1 = ;

    LL ans2 = ;

    LL mx=max(n-m,m); //这个也是必要的。能约就约最大的那个

    LL mi=n-mx;

    for (int i = ; i <= mi; ++i)

    {

        ans1 = ans1*(mx+i)%MOD;

        ans2 = ans2*i%MOD;

    }

    return (ans1*quick_pow(ans2,MOD-,MOD)%MOD); //这里放到最后进行,不然会很慢

}

void work ()

{

    if (i==)

    {

        printf ("%lld\n",a);

        return;

    }

    LL ans = (C(m+i-,m,MOD)*a%MOD+C(m+i-,i-,MOD)*d%MOD)%MOD;

    printf ("%lld\n",ans);

    return ;

}

int main()

{

#ifdef local

    freopen("data.txt","r",stdin);

#endif

    while (scanf("%lld%lld%lld%lld",&a,&d,&m,&i)!=EOF) work();

    return ;

}