[hdu6987]Cycle Binary

定义$x$为$s$的周期，当且仅当$\forall 1\le i\le |s|-x,s_{i}=s_{i+x}$（字符串下标从1开始）

令$per(s)$为$s$的正周期构成的集合，$\min per(s)$为$s$的最小正周期，显然$\max k=\lfloor\frac{n}{\min per(s)}\rfloor$

由此，不妨枚举$\min per(s)$，令$f(x)$为$\min per(s)=x$的$s$个数，则答案即$\sum_{i=1}^{n}\lfloor\frac{n}{i}\rfloor f(i)$

关于如何计算$f(i)$，必要条件为$i\in per(s)$，共有$2^{i}$种方案，再去掉$\min per(s)<i$的方案即可

结论：若$x,y\in per(s)$且$x+y\le |s|$，则$\gcd(x,y)\in per(s)$

不妨假设$x<y$，考虑$1\le i\le |s|-(y-x)$，对$i$分类讨论：

1.若$1\le i\le x$，则$i+y\le |s|$，即有$s_{i}=s_{i+y}=s_{i+(y-x)}$

2.若$x<i\le |s|-(y-x)$，即有$s_{i}=s_{i-x}=s_{i+(y-x)}$

综上，可得$y-x\in per(s)$

注意到$\gcd(x,y)=\gcd(x,y-x)$，由此归纳即得证

由此，对于$i\le \lfloor\frac{n}{2}\rfloor$的$f(i)$，若$j=\min per(s)<i$，显然$i+j\le n$，根据此结论即$\gcd(i,j)\in per(s)$，进而不难得到$j=\gcd(i,j)\mid i$

同时若$\min per(s)\mid i$一定有$i\in per(s)$，那么转移即为$f(i)=2^{i}-\sum_{d\mid i,d<i}f(d)$

对于$i>\lfloor\frac{n}{2}\rfloor+1$的$f(i)$，显然其贡献系数为1且$\sum_{i=1}^{n}f(i)=2^{n}$，因此贡献和即$2^{n}-\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}f(i)$

综上，问题即求$2^{n}+\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}(\lfloor\frac{n}{i}\rfloor-1)f(i)$，其中$f(i)=2^{i}-\sum_{d\mid i,d<i}f(d)$

构造$h(x)=2^{x}$和$g(x)=1$，不难发现$h=f*g$，即可进行杜教筛

另外，来分析一下杜教筛的复杂度——

令$S(n)=\{\lfloor\frac{n}{i}\rfloor\}$（其中$1\le i\le n$），对$\le B$的$f$线性筛，复杂度即$B+\sum_{x\in S(n),x>B}\sqrt{x}$

对后者放缩，即为$\int_{i=1}^{\frac{n}{B}}\sqrt{\frac{n}{i}}=\sqrt{n}\sqrt{\frac{n}{B}}=\frac{n}{\sqrt{B}}$，显然取$B=n^{\frac{2}{3}}$最优，即得到$o(n^{\frac{2}{3}})$的复杂度

上面是对通常杜教筛的分析，但在本题中，有两个不同的地方：

1.由于贡献系数不同，并不是求一个前缀和，而是要数论分块后求$\sqrt{n}$个前缀和

但考虑数论分块右端点的式子$r=\frac{n}{\frac{n}{i}}$，显然其也属于$S(n)$，因此并不改变复杂度

2.不能对$f$线性筛，预处理复杂度为$B\log B$，那么取$B=(\frac{n}{\log n})^{\frac{2}{3}}$即可（可以适当再调整）

3.计算时需要使用快速幂，但显然这样的复杂度仅为$\sum_{x\in S(n),x>B}\log n$，可以接受

最终，总复杂度为$o(n^{\frac{2}{3}}\log^{\frac{1}{3}}n)$，可以通过

 1 #include<bits/stdc++.h>

 2 #include<tr1/unordered_map>

 3 using namespace std;

 4 #define N 5000005

 5 #define mod 998244353

 6 #define ll long long

 7 tr1::unordered_map<int,int>F;

 8 int t,n,ans,mi[N],f[N];

 9 int qpow(int n,int m){

10     int s=n,ans=1;

11     while (m){

12         if (m&1)ans=(ll)ans*s%mod;

13         s=(ll)s*s%mod;

14         m>>=1;

15     }

16     return ans;

17 }

18 int calc(int n){

19     if (n<N)return f[n];

20     if (F[n])return F[n];

21     int ans=(qpow(2,n+1)-2+mod)%mod;

22     for(int i=2,j;i<=n;i=j+1){

23         j=n/(n/i);

24         ans=(ans-(ll)(j-i+1)*calc(n/i)%mod+mod)%mod;

25     }

26     return F[n]=ans;

27 }

28 int main(){

29     mi[0]=1;

30     for(int i=1;i<N;i++)mi[i]=2*mi[i-1]%mod;

31     for(int i=1;i<N;i++){

32         f[i]=(f[i]+mi[i])%mod;

33         for(int j=2;i*j<N;j++)f[i*j]=(f[i*j]-f[i]+mod)%mod;

34     }

35     for(int i=1;i<N;i++)f[i]=(f[i]+f[i-1])%mod;

36     scanf("%d",&t);

37     while (t--){

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

39         ans=qpow(2,n);

40         int lst=0;

41         for(int i=1,j;i<=(n>>1);i=j+1){

42             j=n/(n/i);

43             int now=calc(j);

44             ans=(ans+(ll)(n/i-1)*(now-lst+mod))%mod;

45             lst=now;

46         }

47         printf("%d\n",ans);

48     }

49     return 0;

50 }

巴特西

[hdu6987]Cycle Binary

最新文章

热门文章