【GDOI2019Day1模拟2019.4.28】爱乐之城
Description:
题解:
数论组合题,成功区分数论忘光选手。
task1:
直接反演:
然后发现怎么要分块,TLE???
其实可以用调和级数优化,即增加一个n,就枚举约数,更新即可。
但是不要忘了和i互质的数的和可以直接用搞
这个是的
task2:
经典套路了:
这个用调和级数优化即可,同上。
task3:
为task1得到的
为task2得到的
这种肯定下放约数mobius反演啦:
若有两函数:
则
设为当前的
那么预处理:
即可
Code:
#include<bits/stdc++.h>
#define fo(i, x, y) for(int i = x, B = y; i <= B; i ++)
#define ff(i, x, y) for(int i = x, B = y; i < B; i ++)
#define fd(i, x, y) for(itn i = x, B = y; i >= B; i --)
#define pp printf
#define ll long long
using namespace std;
const int N = 4e5 + 5;
int n, m, op, x, a[N];
int bz[N], mu[N], p[N], phi[N], sm[N];
ll s[N], g[N], c[N], cc;
vector<int> d[N];
#define si size()
const int mo = 998244353;
ll gcd(int x, int y) {
return !y ? x : gcd(y, x % y);
}
ll la, sf[N], cnt[N];
int main() {
freopen("lalaland.in", "r", stdin);
freopen("lalaland.out", "w", stdout);
scanf("%d %d %d", &n, &m, &op);
fo(i, 2, m) {
if(!bz[i]) p[++ p[0]] = i, mu[i] = -1, phi[i] = i - 1;
for(int j = 1; i * p[j] <= m; j ++) {
int k = i * p[j]; bz[k] = 1;
if(i % p[j] == 0) { mu[k] = 0; phi[k] = phi[i] * p[j]; break;}
mu[k] = -mu[i];
phi[k] = phi[i] * (p[j] - 1);
}
} mu[1] = phi[1] = 1;
s[1] = 1; s[2] = 5;
fo(i, 3, m) s[i] = (s[i - 1] + (ll) i * i * phi[i]) % mo;
fo(i, 1, m) fo(j, 1, m / i) d[i * j].push_back(i);
fo(i, 1, m) {
ff(j, 0, d[i].si) {
int x = d[i][j];
cc -= mu[x] * c[x] * c[x];
c[x] += mu[i];
cc += mu[x] * c[x] * c[x];
}
g[i] = cc;
}
fo(i, 1, m) fo(j, 1, m / i) sf[i * j] = (sf[i * j] + g[i] * mu[j] + mo) % mo;
fo(i, 1, m) cnt[i] = 1;
fo(i, 1, n) {
scanf("%d", &a[i]);
if(!op) x = a[i]; else x = (19891989ll * la + a[i]) % m + 1;
a[i] = x;
ff(j, 0, d[x].si) {
int y = d[x][j];
la -= (cnt[y] - 1) * sf[y] % mo;
cnt[y] = cnt[y] * (s[x] + 1) % mo;
la += (cnt[y] - 1) * sf[y] % mo;
}
la = (la % mo + mo) % mo;
if(op) pp("%lld\n", la);
}
if(!op) pp("%lld\n", la);
}