【GDOI2019Day1模拟2019.4.28】爱乐之城

Description:

【GDOI2019Day1模拟2019.4.28】爱乐之城

题解:

数论组合题,成功区分数论忘光选手。

task1:
i=1nj=1nij[(i,j)=1]\sum_{i=1}^n \sum_{j=1}^n i*j*[(i,j)=1]
直接反演:
d=1nμ(d)(di,i<=n)2\sum_{d=1}^n\mu(d)*(\sum_{d|i,i<=n})^2
然后发现怎么要分块,TLE???
其实可以用调和级数优化,即增加一个n,就枚举约数,更新即可。

但是不要忘了和i互质的数的和可以直接用ϕ\phi

=(i=1nj=1iij[(i,j)=1])21=(\sum_{i=1}^n\sum_{j=1}^ii*j*[(i,j)=1])*2-1
=i=1ni2ϕ(i)1=\sum_{i=1}^ni^2*\phi(i)-1
这个是O(n)O(n)

task2:
i=1nj=1nμ(ij)\sum_{i=1}^n\sum_{j=1}^n\mu(i*j)
经典套路了:
=i=1nj=1nμ(ij)[(i,j)=1]=\sum_{i=1}^n\sum_{j=1}^n\mu(i*j)*[(i,j)=1]
=d=1nμ(d)(diμ(i))2=\sum_{d=1}^n\mu(d)*(\sum_{d|i}\mu(i))^2
这个用调和级数优化即可,同上。

task3:
s(n)s(n)为task1得到的
g(n)g(n)为task2得到的
ans=TSg(gcd(T))s[aT]ans=\sum_{T∈S}g(gcd(T))*\prod s[a∈T]

这种肯定下放约数mobius反演啦:
若有两函数f,gf,g
f(d)=dig(i)f(d)=\sum_{d|i}g(i)
g(d)=dif(i)μ(i/d)g(d)=\sum_{d|i}f(i)*\mu({i/d})

cnt[d]cnt[d]为当前的dx(s[x]+1)\prod_{d|x}(s[x]+1)
Ans=d=1ng(d)dicnt[i]μ(i/d)Ans=\sum_{d=1}^n g(d)*\sum_{d|i}cnt[i]*\mu(i/d)
=icnt[i]dig(d)μ(i/d)=\sum_{i}cnt[i]*\sum_{d|i}g(d)*\mu(i/d)

那么预处理:
sf(i)=dig(d)μ(i/d)sf(i)=\sum_{d|i}g(d)*\mu(i/d)即可

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);
}