前缀和

题目

题目描述
自从 lyc 学了前缀和后，他就一直在想：前缀和这么厉害，能拿来玩一年吗？

于是他给了你一个看上去要算一年的任务：对序列 A 求 m 次前缀和， 求出它的第 n 项（规定下标从 0 开始）。 其中，序列 A 为：

A=a0,0,0,0,⋯,0

即第 0 个数为 a0，其余数均为 0。保证 a0 为正整数。

由于答案可能很大，所以结果对 100003 取余。

输入
本题包含多组询问。

第一行输入一个整数 T，表示数据组数。

对于每组数据，输入一行三个整数 n，m，a0，含义均在题目描述中提到。

输出
对于每组询问，输出包含一行一个正整数表示答案。

样例
输入
2
4 2 3
2 0 1
输出
15
0
解释
对于第一个询问，一开始，序列为：
3,0,0,0,0
求了第一次前缀和后，序列为：
3,3,3,3,3
求了第二次前缀和后，序列为：
3,6,9,12,15
所以输出 15，注意下标从 0 开始。

对于第二个询问，答案显然为 0。

数据规模与约定
本题采用子任务测试的形式。 仅当你通过了子任务中所有的测试点， 你才能得到该子任务对应的分数，否则不得分。

对于 100% 的数据，T≤10^4，0≤a<10^5+3。

子任务 1（24 分）：n,m≤100。

子任务 2（5 分）：n=1，m≤50000。

子任务 3（30 分）：n,m≤50000，T=1。

子任务 4（41 分）：n,m≤50000。

子任务 5（100 分）：n,m≤10^18。

提示
注意边界。

---

题解

–看到这道题，当然是果断的暴力模拟，因为根本没有思路，可以得29分
然后美丽打表，找到神奇规律，答案就是a0 * C（m−1，n+m−1 ），哦拉拉诶
但是求组合数是绝对要有除法的，再加上要取模，所以说补充一个除法取模公式：
a/b=a * b^(mod-2) %mod ;
其实就是求逆元，当然要用快速幂
可以预处理阶乘和逆元，降低时间复杂度

但是子任务五确实不会耶，谁叫我蒟蒻呢
大佬说用Lucas 定理，宝宝不会，就交给你们咯

---

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXN=50005;
const int mod=100003;

long long t;
long long n,m,a;
long long x[100005],mul[100005];

long long Pow(long long a,long long b){
    long long ans=1;
    while(b){
        if(b&1)
            ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans%mod;
}

long long C(long long r,long long k){
    long long ans=mul[k];
    ans=ans*x[mul[r]]%mod;
    ans=ans*x[mul[k-r]]%mod;
    return ans%mod;
}

int main(){
    cin>>t;
    for(int i=1;i<=100005;i++)
        x[i]=Pow(i,mod-2);
    mul[0]=1;
    mul[1]=1;
    for(int i=2;i<=100000;i++)
        mul[i]=mul[i-1]*i%mod;
    while(t--){
        scanf("%lld%lld%lld",&n,&m,&a);
        if(m==0){
            if(n==0)
                printf("%lld\n",a);
            else
                printf("0\n");
        }
        else
            printf("%lld\n",a*C(m-1,n+m-1)%mod);
    }
    return 0;
}