2018牛客暑假多校第十场

这道题是以前做过的求 $K$K 次前缀和再带上修改的题，做这个之前最好先看看这两道：
① $K$K 次前缀和：https://www.nowcoder.com/acm/contest/109/C
② $K$K次逆前缀和：https://www.nowcoder.com/acm/contest/117/B

方法就是修改后的矩阵快速幂 或者 组合数公式 来做
0次前缀和： $a1,a2,a3,a4,a5$a1,a2,a3,a4,a5
1次前缀和： $a1，a1+a2，a1+a2+a3，a1+a2+a3+a4，a1+a2+a3+a4+a5$a1，a1+a2，a1+a2+a3，a1+a2+a3+a4，a1+a2+a3+a4+a5
2次前缀和： $a1，2\ast a1+a2，3\ast a1+2\ast a2+a3，4\ast a1+3\ast a2+2\ast a3+a4，5\ast a1+4\ast a2+3\ast a3+2\ast a4+a5$a1，2∗a1+a2，3∗a1+2∗a2+a3，4∗a1+3∗a2+2∗a3+a4，5∗a1+4∗a2+3∗a3+2∗a4+a5
3次前缀和： $a1，3\ast a1+a2，6\ast a1+3\ast a2+a3，10\ast a1+6\ast a2+3\ast a3+a4，15\ast a1+10\ast a2+6\ast a3+3\ast a4+a5$a1，3∗a1+a2，6∗a1+3∗a2+a3，10∗a1+6∗a2+3∗a3+a4，15∗a1+10∗a2+6∗a3+3∗a4+a5
4次前缀和： $a1，4\ast a1+a2，10\ast a1+4\ast a2+a3，20\ast a1+10\ast a2+4\ast a3+a4，35\ast a1+20\ast a2+10\ast a3+4\ast a4+a5$a1，4∗a1+a2，10∗a1+4∗a2+a3，20∗a1+10∗a2+4∗a3+a4，35∗a1+20∗a2+10∗a3+4∗a4+a5
像 $K$K 次前缀和的组合数公式就是：
$C_{K-1+y-x}^{K-1}$CK−1+y−xK−1​
表示的就是 $x$x 这个位置上的值，加了这么多次到 $y$y 这个位置上

我们用差分记录下每次的修改，并且记录下这是第几次修改的，于是就可以求得那次修改的值到现在经过了多少次前缀和

而询问区间和的时候就只有一个一个暴力计算，所以他才要求询问次数会小于 $500$500

#include"bits/stdc++.h"
#define out(x) cout<<#x<<"="<<x
#define C(n,m) (m>n?0:(long long)fac[(n)]*invf[(m)]%MOD*invf[(n)-(m)]%MOD)
using namespace std;
typedef long long LL;
const int maxn=1e6+5;
const int MOD=998244353;
LL ksm(LL a,LL b,LL mod)
{
	LL res=1,base=a;
	while(b)
	{
		if(b&1)res=(res*base)%mod;
		base=(base*base)%mod;
		b>>=1;
	}
	return res;
}
LL fac[maxn]={1,1},invf[maxn]={1,1};
void InitFac(int n)
{
	for(int i=2;i<=n;i++)fac[i]=fac[i-1]*i%MOD;
	invf[n]=ksm(fac[n],MOD-2,MOD);
	for(int i=n-1;i>=2;i--)invf[i]= invf[i+1]*(i+1)%MOD;
}
int N,M,K,cnt;
struct AAA
{
	LL x,k,v;
	AAA(){}
	AAA(LL x,LL k,LL v):x(x),k(k),v(v){}
};
AAA a[maxn];
LL query(int pos)//计算[1,pos]的前缀和 
{
	LL res=0;
	for(int i=1;i<=cnt;i++)
	{
		LL x=a[i].x;
		LL k=a[i].k;
		LL v=a[i].v;
		if(x<=pos)
		{
			int len=pos-x;
			res+=C(K-k+len,K-k)*v;	//②K是当前弄的前缀和的次数，k是那个差分的时候的前缀和次数，所以K-k就是这个值从那个时候到现在的前缀和次数 
			res%=MOD;
		}
	}
	return res;
}
int main()
{
	InitFac(maxn-5);
	int T;
	cin>>T;
	while(T--)
	{
		K=0;//存总共弄了几次前缀和 
		cin>>N>>M;
		cnt=0;
		for(int i=1;i<=M;i++)
		{
			int cmd,L,R,v;
			scanf("%d",&cmd);
			if(cmd==1)
			{
				scanf("%d%d%d",&L,&R,&v);
				a[++cnt]=AAA(L,K-1,v);		//①因为是差分来保存的，所以要减一个前缀和 
				a[++cnt]=AAA(R+1,K-1,-v);
			}
			else if(cmd==2)K++;
			else
			{
				scanf("%d%d",&L,&R);
				cout<<((query(R)-query(L-1))%MOD+MOD)%MOD<<endl;
			}
		}
	}
}