Cowslip Collections
我们记 \(f_i\) 为 \(gcd\) 恰好为 \(i\) 的方案数。
然后我们的答案就是 \(\sum\limits_{i=1}^{1000000}i\times f_i\)
不过这个 \(f_i\) 显然是不好求的，我们记 \(g_i\) 为 \(gcd\) 为 \(i\) 的倍数的方案数。
那么有 \(g_i=\sum\limits_{i|j} f_j=C_{cnt[d]}^k\) ，\(cnt_i\) 表示存在 \(i\) 因子的数的个数
然后我们的 \(f\) 就可以根据 \(g\) 反演得到 \(f_i=\sum\limits_{i|j} \mu (\frac ji)\times g_j\)
然后我们的答案就变成了 \(\sum\limits_{i=1}^{1000000}i\sum\limits_{i|j} \mu (\frac ji)\times g_j=\sum\limits_{i=1}^{1000000}\sum\limits_{i|j} i\times \mu (\frac ji)\times g_j\)
然后我们考虑每加进来一个数的变化量。
\(C_{cnt[d]+1}^k-C_{cnt[d]}^k\)
然后转变一下我们答案的贡献形式
\(\sum\limits_{i=1}^{1000000}\sum\limits_{i|j} i\times \mu (\frac ji)\times g_j=\sum\limits_{i=1}^{1000000}\sum\limits_{j|i} j\times \mu (\frac ij)\times g_i=\sum\limits_{i=1}^{1000000}g_i\sum\limits_{j|i} j\times \mu (\frac ij)\)
后面的那个求和式就是 \(\mu *ID=\phi\) ，所以最后答案就变成了。
\(\sum\limits_{i=1}^{1000000}g_i\times \phi\)
那么每次我们只考虑变化量，也就是说只需要对 \(x\) 的因子进行操作即可。
时间复杂度 \(O(n\sqrt n)\)
点击查看代码
#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const int N=1e6+10,MODD=1e9+7;
int phi[N],prime[N],cnt;
LL pw[N],inv[N];
bool sf[N];
LL ksm(LL x,LL y) {
LL ret=1;
while(y) {
if(y&1) ret=ret*x%MODD;
x=x*x%MODD;
y>>=1;
}
return ret;
}
LL C(LL x,LL y) {
if(x<y) return 0;
return pw[x]*inv[x-y]%MODD*inv[y]%MODD;
}
LL add(LL x,LL y) {
return (x+y>=MODD?x+y-MODD:x+y);
}
void init() {
pw[0]=inv[0]=1; phi[1]=1;
for(int i=1;i<=N-10;++i) pw[i]=pw[i-1]*i%MODD;
inv[N-10]=ksm(pw[N-10],MODD-2);
for(int i=N-11;i>=1;--i) inv[i]=inv[i+1]*(i+1)%MODD;
sf[1]=1;
for(int i=2;i<=N-10;++i) {
if(!sf[i]) {
prime[++cnt]=i;
phi[i]=i-1;
}
for(int j=1;j<=cnt;++j) {
int t=prime[j]*i;
if(t>N-10) break;
sf[t]=1;
if(i%prime[j]==0) {
phi[t]=phi[i]*prime[j];
break;
}
else {
phi[t]=phi[i]*(prime[j]-1);
}
}
}
}
int n,k,q;
LL ans,sum[N];
void calc(int x) {
(ans+=add(C(sum[x]+1,k),MODD-C(sum[x],k))%MODD*phi[x]%MODD)%=MODD;
++sum[x];
}
void insert(int x) {
int R=sqrt(x);
for(int i=1;i<=R;++i) {
if(x%i==0) {
calc(i);
if(i*i!=x) calc(x/i);
}
}
}
int main () {
init();
scanf("%d%d%d",&n,&k,&q);
for(int i=1;i<=n;++i) {
int x;
scanf("%d",&x);
insert(x);
}
for(int i=1;i<=q;++i) {
int x;
scanf("%d",&x);
insert(x);
printf("%lld\n",ans);
}
return 0;
}
Xor-matic Number of the Graph
这题很早之前就做过了，所以不想讲。
Region Separation
神题。
首先我们记所有 \(a\) 的和为 \(S\) ，那么显然只有当分成的块的和 \(x\) 必须要满足 \(x|S\) ，才可能凑出那种分法。
然后这里需要知道一个结论，对于一个 \(x\) ，他的砍树方法是固定的，因为你从子树走上来，出现子树和为 \(x\) 就砍掉，如此往复，肯定是固定的。
而我们有一个结论，当满足 \(sz_i\) （\(sz_i\) 表示 \(i\) 子树中 \(a\) 的和）为 \(x\) 的倍数的数有 \(\frac Sx\) 个时，我们一定可以构造出一种砍树方案，这个是比较显然的，直接好像碰到过，不过不记得在哪里见过了。
但是如果我们考虑枚举 \(x\) ，就会发现由于 \(S\) 比较大，这是不能枚举的，但是因为至多只有 \(n\) 个数，也就是至多分成 \(n\) 段，所以我们枚举分成 \(x\) 段，那么每段的和就是 \(\frac Sx\) 。
我们考虑点 \(u\) 能分成哪些符合条件的连通块。
而对于一些 \(sz_u=p\times \frac Sx\) 我们移项可以得到 \(x=p\times \frac S{sz_u}\)
那么也就是说对于一个子树而言它可以为 \(x=\frac S{gcd(S,sz_u)}\) 这样的 \(x\) 以及他的倍数造成贡献，能够造出这样的连通块。（为什么取 \(gcd(S,sz_u)\) 呢，因为你肯定得是 \(S\) 的因数不然不可能成功）
然后倍数关系就好处理了，我们统计一下每种 \(x\) 被贡献了多少次，记为 \(g\) 。
然后对满足 \(g_x=x\) 的那些段数就称为满足条件的。
然后如何计算答案呢，记 \(f_i\) 表示目前分了 \(i\) 段，然后继续往下分的方案数。
也就是把原题的分裂改为合并。
那么有以下转移
\(f_i=(\sum\limits_{i|j}f_j+1)\times [g_i==i]\)
最后答案就是 \(f_1\)
时间复杂度 \(O(n\ln n+n\log a)\)
点击查看代码
#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const int MAXN=1e6+10,MODD=1e9+7;
int n;
int a[MAXN],Fa[MAXN];
LL sum[MAXN];
vector<int> e[MAXN];
void add(int f,int t) {
e[f].push_back(t);
}
LL gcd(LL x,LL y) {
return (!y?x:gcd(y,x%y));
}
LL g[MAXN],f[MAXN];
int main () {
scanf("%d",&n);
for(int i=1;i<=n;++i) {
scanf("%d",&a[i]);
}
for(int i=2;i<=n;++i) {
scanf("%d",&Fa[i]);
}
for(int i=n;i>=1;--i) {
sum[i]+=a[i];
sum[Fa[i]]+=sum[i];
}
for(int i=1;i<=n;++i) {
LL ls=gcd(sum[1],sum[i]);
if(sum[1]/ls<=n) ++g[sum[1]/ls];
}
for(int i=n;i;--i) {
for(int j=i*2;j<=n;j+=i) {
g[j]=(g[j]+g[i])%MODD;
}
}
for(int i=n;i;--i) {
if(g[i]!=i) continue;
f[i]=1;
for(int j=i*2;j<=n;j+=i) {
f[i]=(f[i]+f[j])%MODD;
}
}
printf("%lld\n",f[1]);
return 0;
}