多校联测11 模板题

题目大意

给你四个整数$n,m,seed,w$，其中$n,m$为两个多项式$A(x)=\sum _{i=0}^n{a}_i{x}^i$和$B(x)=\sum _{i=0}^m{b}_i{x}^i$的最高次数，$seed,w$是用来生成$a_i$和$b_i$的参数。

设$C(x)=A(x)B(x)=\sum _{i=0}^{n+m}{c}_i{x}^i$。

有$q$次询问，第$i$次输入$l_i,r_i$，求$\sum _{j=l_i}^{r_i}{c}_j$对$1145141999$（$1145141999=2\times 7\times 11\times 13\times 17\times 33647+1$，是一个质数）取模后的值。

构造$a_i$和$b_i$的代码如下，可以对其进行修改来完成此题。

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long u64;
const int p=1145141999;
int a[10000005],b[10000005];
int n,m,q,w;
u64 seed;
u64 rnd()
{u64 x = seed;x ^= x << 13;x ^= x >> 7;x ^= x << 17;return seed = x;
}
int main(){scanf("%d%d%llu%d",&n,&m,&seed,&w);scanf("%d",&q);for(int i=0;i<=n;++i)a[i]=rnd()%w;for(int i=0;i<=m;++i)b[i]=rnd()%w;int l,r;for(int i=1;i<=q;++i){scanf("%d%d",&l,&r);}return 0;
}

$1\le n\le 6\times 10^6,1\le q\le 25,1\le w\le 1145141999$

题解

$C(x)=A(x)B(x)=\sum _{i=0}^{n+m}(\sum _{j=0}^i{a}_j{b}_{i-j})x^i$

也就是说，$c_i=\sum _{j=0}^i{a}_j{b}_{i-j}$。

那么，$\sum _{i=0}^t{c}_i=\sum _{i=0}^t\sum _{j=0}^i{a}_j{b}_{i-j}=\sum _{j=0}^t{a}_j\sum _{i=0}^{t-j}{b}_i$

令$b_i$的前缀和为${sum}_i$，$S(t)=\sum _{i=0}^t{a}_i{sum}_{t-i}$，则答案为$S(r)-S(l-1)$。

求$S(t)$的时间复杂度为$O(n)$，所以总时间复杂度为$O(nq)$。

code

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long u64;
const long long p=1145141999;
int a[20000005],b[20000005],sum[20000005];
int n,m,q,w;
u64 seed;
u64 rnd()
{u64 x = seed;x ^= x << 13;x ^= x >> 7;x ^= x << 17;return seed = x;
}
long long gt(int t){long long re=0;for(int i=0;i<=t;i++){re=(re+1ll*a[i]*sum[t-i])%p;}return re;
}
int main(){scanf("%d%d%llu%d",&n,&m,&seed,&w);scanf("%d",&q);for(int i=0;i<=n;++i)a[i]=rnd()%w;for(int i=0;i<=m;++i)b[i]=rnd()%w;sum[0]=b[0];for(int i=1;i<=n+m;i++) sum[i]=(1ll*sum[i-1]+b[i])%p;int l,r;for(int i=1;i<=q;++i){scanf("%d%d",&l,&r);printf("%lld\n",(gt(r)-gt(l-1)+p)%p);}return 0;
}