• 周一. 8月 15th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

[hdu6987]Cycle Binary

admin

11月 28, 2021

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

令$per(s)$为$s$的正周期构成的集合,$min per(s)$为$s$的最小正周期,显然$max k=lfloorfrac{n}{min per(s)}floor$

由此,不妨枚举$min per(s)$​,令$f(x)$​为$min per(s)=x$​的$s$​个数,则答案即$sum_{i=1}^{n}lfloorfrac{n}{i}floor f(i)$​

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

结论:若$x,yin per(s)$​​​且$x+yle |s|$​​​,则$gcd(x,y)in per(s)$​

不妨假设$x<y$​,考虑$1le ile |s|-(y-x)$,对$i$​分类讨论:

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

2.若$x<ile |s|-(y-x)$​,即有$s_{i}=s_{i-x}=s_{i+(y-x)}$

综上,可得$y-xin per(s)$

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

由此,对于$ile lfloorfrac{n}{2}floor$​​​​​的$f(i)$​​​​,若$j=min per(s)<i$​​​​,显然$i+jle n$​​​​,根据此结论即$gcd(i,j)in per(s)$​​​​,进而不难得到$j=gcd(i,j)mid i$​​​

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

对于$i>lfloorfrac{n}{2}floor+1$​​​的$f(i)$​​​,显然其贡献系数为1且$sum_{i=1}^{n}f(i)=2^{n}$​​​,因此贡献和即$2^{n}-sum_{i=1}^{lfloorfrac{n}{2}floor}f(i)$​​

综上,问题即求$2^{n}+sum_{i=1}^{lfloorfrac{n}{2}floor}(lfloorfrac{n}{i}floor-1)f(i)$​​​,其中$f(i)=2^{i}-sum_{dmid i,d<i}f(d)$​

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

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

令$S(n)={lfloorfrac{n}{i}floor}$​​​​​(其中$1le ile n$​​​​​),对$le B$​​的$f$​​线性筛,复杂度即$B+sum_{xin 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$​​线性筛,预处理复杂度为$Blog B$​​,那么取$B=(frac{n}{log n})^{frac{2}{3}}$​​​​​​即可(可以适当再调整)

3.计算时需要使用快速幂,但显然这样的复杂度仅为$sum_{xin 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
",ans);
48     }
49     return 0;
50 }

View Code

发表回复

您的电子邮箱地址不会被公开。