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

D Rikka with Prefix Sum —— 组合数

程序员文章站 2024-03-15 21:34:42
...

Prefix Sum is a useful trick in data structure problems.

For example, given an array A of length n and m queries. Each query gives an interval [l,r] and you need to calculate . How to solve this problem in O(n+m)? We can calculate the prefix sum array B in which Bi is equal to . And for each query, the answer is Br-Bl-1.

Since Rikka is interested in this powerful trick, she sets a simple task about Prefix Sum for you:

Given two integers n,m, Rikka constructs an array A of length n which is initialized by Ai = 0. And then she makes m operations on it.

There are three types of operations:
1. 1 L R w, for each index i ∈ [L,R], change Ai to Ai + w.
2. 2, change A to its prefix sum array. i.e., let A’ be a back-up of A, for each i ∈ [1,n], change Ai to .
3. 3 L R, query for the interval sum .
输入描述:
The first line contains a single number t(1≤ t ≤ 3), the number of the testcases.

For each testcase, the first line contains two integers n,m(1 ≤ n,m ≤ 105).

And then m lines follow, each line describes an operation(1 ≤ L ≤ R≤ n, 0 ≤ w ≤ 109).

The input guarantees that for each testcase, there are at most 500 operations of type 3.
输出描述:
For each query, output a single line with a single integer, the answer modulo 998244353.
示例1
输入
复制
1
100000 7
1 1 3 1
2
3 2333 6666
2
3 2333 6666
2
3 2333 6666
输出
复制
13002
58489497
12043005

一开始以为是数据结构,大家都以为是数据结构,想了一下发现和之前牛客9的H题好像,然后就迷茫了,不会做。。。
问了别人才知道不是一道难题。
假设一开始全是1,求前缀和之后发现就是组合数。但是题目给你的不是n个1,怎么办?先全部设为1,然后在求的时候减去那些用到了但是没赋值的位置,就好了。
快速求逆元的时候忘记是到0了,一直wa真尴尬。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=998244353;
const ll maxn=2e5+5;
ll jc[maxn],ny[maxn];
ll qpow(ll a,ll b)
{
    ll ans=1,ret=a;
    while(b)
    {
        if(b&1)
            ans=(ans*ret)%mod;
        ret=(ret*ret)%mod;
        b>>=1;
    }
    return ans;
}
void init()
{
    jc[0]=1;
    for(ll i=1;i<maxn;i++)
        jc[i]=(jc[i-1]*i)%mod;
    ny[maxn-1]=qpow(jc[maxn-1],mod-2);
    for(ll i=maxn-2;i>=0;i--)
        ny[i]=ny[i+1]*(i+1)%mod;
}
ll c(ll n,ll m)
{
    if(m<0||m>n)
        return 0;
    return jc[n]*ny[m]%mod*ny[n-m]%mod;
}
ll query(ll l,ll r,ll k,ll sta)
{
    l-=sta,r-=sta;
    return (c(r+k,r)-c(l+k-1,l-1)+mod)%mod;//根据组合的性质可知一排相加就等于下一排的末尾的数
}
ll a[maxn],le[maxn],rig[maxn],val[maxn];
int main()
{
    int t;
    scanf("%d",&t);
    init();
    while(t--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        int cnt=0;
        ll q,l,r;
        memset(a,0,sizeof(a));
        while(m--)
        {
            scanf("%lld",&q);
            if(q==1)
                ++cnt,scanf("%lld%lld%lld",&le[cnt],&rig[cnt],&val[cnt]);
            else if(q==2)
                a[cnt]++;
            else
            {
                scanf("%lld%lld",&l,&r);
                ll pos=0,ans=0;

                for(int i=cnt;i>=1;i--)//2的运算是从后往前递增的
                {
                    pos+=a[i];
                    if(le[i]<=r)
                        ans=(ans+val[i]*query(max(l,le[i]),r,pos+1,le[i])%mod)%mod;
                        //因为c是从1开始的,所以pos要加1
                    if(rig[i]+1<=r)
                        ans=(ans-val[i]*query(max(l,rig[i]+1),r,pos+1,rig[i]+1)%mod+mod)%mod;
                }
                printf("%lld\n",ans);
            }
        }
    }
    return 0;
}
/*
100000 7
1 1 3 1
2
3 2333 6666
2
3 2333 6666
2
3 2333 6666
*/
相关标签: 组合