Curious Array CodeForces - 407C (高阶差分)

高阶差分板子题

const int N = 1e5+111;
int a[N], n, m, k;

int C[N][111], d[N][111];

signed main() {
	scanf("%d%d", &n, &m);
	REP(i,1,n) scanf("%d", a+i);
	REP(i,0,n+100) {
		C[i][0]=1;
		REP(j,1,100) C[i][j]=(C[i-1][j]+C[i-1][j-1])%P;
	}
	REP(i,1,m) {
		int l, r, k;
		scanf("%d%d%d", &l, &r, &k);
		int mx = min(r-l,k);
		REP(j,0,mx) (d[l+j][j]+=C[k][k-j])%=P;
		REP(j,0,mx) (d[r+1][j]+=(P-C[r-l-j+k][k-j])%P)%=P;
	}
	PER(j,0,100) REP(i,1,n) { 
		(d[i][j]+=(d[i][j+1]+d[i-1][j])%P)%=P;
	}
	REP(i,1,n) printf("%d ",(d[i][0]+a[i])%P);hr;
}