BZOJ3632: 外太空旅行

BZOJ1547: 周末晚会

https://lydsy.com/JudgeOnline/problem.php?id=1547

分析:

对于一个串旋转若干次会回到本身，旋转次数即是同构个数，这个东西和最小整除周期有关。
设\(f_i\)表示有多少个串的最小整除周期是\(i\)，\(g_i=\sum\limits_{j|i}f_j,f_i=\sum\limits_{j|i}g_j\mu(i/j)\)。
那么答案就是\(\sum\limits_{i|n}\frac{f_i}{i}\)。
当\(n\le K\)时，\(g_i=2^i\)，否则，考虑求一个\(h_i\)表示长度为\(i\)重复出现次数小于等于\(K\)的个数(内部)，求\(h\)前缀和优化一下\(O(n)\)求，那么枚举最长前缀1+最长后缀1的个数\(j\)，可得\(g_i=\sum\limits_{j=0}^{K}(j+1)\times h_{i-j-2}\)，这个也可以前缀和优化一下\(O(1)\)求。
考虑到有用的\(f,g\)一共约数个数个，时间复杂度为\(O(n+\sigma(n)^2)\)。

代码:

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cstdlib>

using namespace std;

#define mod 100000007

#define N 2050

#define M 2050

typedef long long ll;

int n,K;

ll f[N],g[N];

int pri[M],cnt,mu[M];

bool vis[M];

int w[N],tot,mi[M],h[M],sum[M],sum2[M];

void ins(int x) {

	w[++tot]=x;

}

ll qp(ll x,ll y) {

	ll re=1; for(;y;y>>=1,x=x*x%mod) if(y&1) re=re*x%mod; return re;

}

void sieve() {

	int i,j;

	mu[1]=1;

	for(i=2;i<=n;i++) {

		if(!vis[i]) {

			pri[++cnt]=i; mu[i]=-1;

		}

		for(j=1;j<=cnt&&i*pri[j]<=n;j++) {

			vis[i*pri[j]]=1;

			if(i%pri[j]==0) {

				mu[i*pri[j]]=0; break;

			}

			mu[i*pri[j]]=-mu[i];

		}

	}

}

int main() {

	int T;

	scanf("%d",&T);

	while(T--) {

	scanf("%d%d",&n,&K);

	cnt=0;

	if(n<=K) {

		memset(f,0,sizeof(f));

		int i,j;

		sieve();

		for(mi[0]=i=1;i<=n;i++) mi[i]=mi[i-1]*2%mod;

		for(i=1;i<=n;i++) for(j=i;j<=n;j+=i) {

			f[j]=(f[j]+mi[i]*mu[j/i])%mod;

		}

		int ans=0;

		for(i=1;i<=n;i++) if(n%i==0) ans=(ans+f[i]*qp(i,mod-2))%mod;

		printf("%d\n",(ans%mod+mod)%mod);

		continue;

	}else {

		memset(h,0,sizeof(h));

		memset(f,0,sizeof(f));

		memset(h,0,sizeof(h));

		tot=0;

		int i,j;

		for(i=1;i*i<=n;i++) {

			if(n%i==0) {

				ins(i); if(n/i!=i) ins(n/i);

			}

		}

		sieve();

		for(mi[0]=i=1;i<=n;i++) mi[i]=mi[i-1]*2%mod;

		h[0]=1; sum[0]=1;

		for(i=1;i<=K;i++) h[i]=mi[i],sum[i]=(sum[i-1]+h[i])%mod;

		for(i=K+1;i<=n;i++) {

			if(i>K+1) h[i]=(sum[i-1]-sum[i-K-2]+mod)%mod;

			else h[i]=sum[i-1];

			sum[i]=(sum[i-1]+h[i])%mod;

		}

		for(i=0;i<=n;i++) sum2[i]=(sum2[i-1]+ll(n-i)*h[i])%mod;

		for(i=1;i<=tot;i++) {

			if(w[i]<=K+1) g[i]=mi[w[i]]-1;

			else {

				/*for(j=0;j<=K;j++) {

					g[i]=(g[i]+ll(j+1)*h[w[i]-j-2])%mod;

				}*/

				ll ss2,ss1;

				if(w[i]>K+2) ss2=sum2[w[i]-2]-sum2[w[i]-K-3],ss1=sum[w[i]-2]-sum[w[i]-K-3];

				else ss2=sum2[w[i]-2],ss1=sum[w[i]-2];

				g[i]=((ss2-ll(n-w[i]+1)*ss1)%mod+mod)%mod;

				//g[i]=((sum2[w[i]-2]-sum2[w[i]-K-2]-ll(n-w[i]+1)*(sum[w[i]-2]-sum[w[i]-K-2]))%mod+mod)%mod;

			}

		}

		for(i=1;i<=tot;i++) {

			for(j=1;j<=tot;j++) if(w[j]%w[i]==0) {

				f[j]=(f[j]+g[i]*mu[w[j]/w[i]])%mod;

			}

		}

		int ans=0;

		for(i=1;i<=tot;i++) ans=(ans+ll(f[i])*qp(w[i],mod-2))%mod;

		printf("%d\n",(ans%mod+mod)%mod);

		continue;

	}

	}

}

巴特西

BZOJ3632: 外太空旅行

BZOJ1547: 周末晚会

最新文章

热门文章