Project Euler 728 题解

曾梵瑀 / 2024-10-12 / 原文

Problem 728 Circle of Coins

得到 Wallbreaker5th 的指导。

$F$ 就是求这些环上区间（记为 $A$）的异或线性基大小。令 $A'_i\gets A_i\oplus A_{i+1}$。现在求 $\lang A'\rang$ 的线性基。如果可能从全黑和全白间转换，那么 $\dim \lang A'\rang=\lang A\rang-1$，否则不 $-1$。这个转换的条件是 $\frac k{(n,k)}\equiv 1 \pmod 2$。

接下来观察到 $A'_i,A'_{i+k\bmod n},A'_{i+2k\bmod n}\dots$ 覆盖到的集合对于不同等价类（$i,i+k\dots$ 在一个等价类）无交。因此这些是独立的。

对于一个等价类去掉无法覆盖到的位置，等价类就形如 $110000,011000,001100,\dots 100001$，有 $\frac n{(n,k)}$ 个向量。线性基的大小是：$\frac n{(n,k)}-1$，这是显然的。所以得到：

\[F(n,k)=2^{n-(n,k)+[\frac k{(n,k)}\equiv 1 \pmod 2]} \]

尝试计算答案。

\[S(N)=\sum _{n=1}^N 2^n\sum_{d\mid n} 2^{-d}\sum _{d\mid k}2^{[V_2(d)=V_2(k)]}\sum_{t\mid(\frac kd ,\frac nd)}\mu (t)\\ =\sum_{n=1}^N 2^n\sum_{d\mid n}2^{-d}\sum_{dt\mid n}\mu(t)\sum_{k=1}^{\frac n{dt}}2^{kt\bmod 2} \]

所以可以直接卷积 $O(n\log n)$ 解决。应该是可以 $O(n\log\log n)$ 的，未知线性行不行。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e7+5,mod=1e9+7;
int pw[maxn],ipw[maxn],mu[maxn],n,F[maxn],G[maxn],H[maxn],inv[maxn];
bool isp[maxn];vector<int> pr;
int qp(int a,int b){
	if(b==0)return 1;
	int T=qp(a,b>>1);T=T*T%mod;
	if(b&1)T=T*a%mod;
	return T;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n;mu[1]=1;
	for(int i=2;i<=n;i++){
		if(!isp[i])mu[i]=-1,pr.push_back(i);
		for(auto u:pr){
			if(i*u>n)break;
			isp[i*u]=1;
			if(i%u==0){
				mu[i*u]=0;
				break;
			}
			mu[i*u]=-mu[i];
		}
	}
	pw[0]=1;pw[1]=2;ipw[0]=1,ipw[1]=(mod+1)/2;
	for(int i=2;i<=n;i++)pw[i]=pw[i-1]*2%mod,ipw[i]=ipw[i-1]*ipw[1]%mod;
	for(int i=1;i<=n;i++)inv[i]=qp(i,mod-2);
	for(int i=1;i<=n;i++)for(int j=i;j<=n;j+=i)(F[j]+=ipw[i]*mu[j/i])%=mod;
	for(int i=1;i<=n;i++)G[i]=i;
	for(int i=1;i<=n;i++)for(int j=i;j<=n;j+=i)(H[j]+=G[i]*F[j/i])%=mod;
	int ans=0;for(int i=1;i<=n;i++)(ans+=pw[i]*H[i])%=mod;
	for(int i=1;i<=n;i++)F[i]=0,H[i]=0;
	for(int i=1;i<=n;i++)for(int j=i;j<=n;j+=i)(F[j]+=ipw[i]*mu[j/i]*((j/i)&1))%=mod;
	for(int i=1;i<=n;i++)G[i]=(i+1)/2;
	for(int i=1;i<=n;i++)for(int j=i;j<=n;j+=i)(H[j]+=G[i]*F[j/i])%=mod;
	for(int i=1;i<=n;i++)(ans+=pw[i]*H[i])%=mod;
	ans=(ans%mod+mod)%mod;
	cout<<ans<<endl;
	return 0;
}