D Rikka with Prefix Sum —— 组合数
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
*/
上一篇: Python之heapq模块
下一篇: python来构建多层网络