#C241015A. 序列生成(sequence)
标签（Label）
- 数学推理
前言（Front talk）
$\qquad$在思考到通过 $O(m\log m)$ ，即转换成值域的时候，考虑到了对于每个 $mod$ 处理对应的数，但是没有想到可以通过 $\sum_{i=l_1}^{i\le r1}a[i] - cnt\times mod\times j$ 的计算方式，即对于每个 $a[i]$ 减去首个小于他的 $mod$ 的倍数，乘上在 $[j\times mod,(j+1)\times mod -1]$ 区间内 $a[i]$ 的数量，可以求出这个区间内 $a[i]$ 对答案的贡献。
网址（Website）
题解（Solution）
出题者题解
算法分析
注意到 $x[i] \mod (x[j] + 1) = x[i] - \left\lfloor \frac{x[i]}{x[j] + 1} \right\rfloor \times (x[j] + 1)$，并且 $(x[j], \left\lfloor \frac{x[i]}{x[j] + 1} \right\rfloor)$ 总个数为 $m \log m$ 级别的。所以如果我们可以得到每个数在序列区间中的出现次数以及区间的和，我们就可以通过枚举 $(x[j], k)$ 点对来快速算出答案。
考虑鸽巢原理，必定存在 $p, q$ 且 $p < q \leq m$ 使得 $x[p] = x[q]$，所以 $x[n]$ 必定是一个循环序列，由此问题就解决了。
时间复杂度 $O(m\log m)$ 。
代码（Code）
#include<bits/stdc++.h>
#include<vector>
#include<queue>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
#define x first
#define y second
inline int rd(){
char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 1012345;
bool ST;
int mod,a,c,x[N],l1,l2,r1,r2,mx;
int buc[N],app[N],p[N];
void solve(){
mod=rd(),a=rd(),c=rd(),x[0]=rd();
l1=rd(),r1=rd(),l2=rd(),r2=rd();
mx = max(r1, r2);
For(i,1,mx) x[i] = (x[i-1]*a+c)%mod;
memset(app, 0, sizeof app);
memset(buc, 0, sizeof buc);
memset(p, 0, sizeof p);
For(i,l1,r1) app[x[i]] += x[i], buc[x[i]]++;//放在值域上
For(i,1,mod) app[i] += app[i-1], buc[i] += buc[i-1];//求前缀和
For(i,l2,r2) p[x[i]+1]++;
int ans = 0;
For(i,0,mod+1){//枚举 x[i]
if(!p[i]) continue;
for(int j = 0; j*i<=mod; j++){//枚举范围
int l = j*i, r = min(mod, (j+1)*i-1);
ans += (app[r] - app[l-1] - j*i*(buc[r]-buc[l-1])) * p[i];
}
}printf("%lld\n",ans);
}
bool ED;
signed main(){
cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
freopen("sequence.in","r",stdin);
freopen("sequence.out","w",stdout);
int T = rd(), Tim = clock();
while(T--) solve();
return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}
