欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

前缀和

程序员文章站 2022-04-02 19:01:57
...

题目

题目描述
自从 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;
}
相关标签: 刷题之路