ABC304F Shift Table

题目大意

小$T$和小$A$要做$n$天的工作。

小$T$的工作表表示为字符串$S$，其中“#”表示当天要工作，“.”表示当天不需要工作。

你需要安排小$A$的工作，步骤如下

• 选择一个$n$的约数$m$，$m\ne n$
• 决定这$m$天的工作安排
• 对于$i=1,2,\dots ,n-m$，第$i+m$天的工作安排和第$i$天的相同

求小$A$有多少种工作安排，使得每一天都至少有一个人在工作？

输出答案模$998244353$后的值。

$2\le n\le 10^5$

题解

首先，枚举$n$的约数，即$m$的值。然后，对于每一个为“.”的位置$i$，小$A$的这个位置都必须是“#”，所以小$A$的所有$k\times m+i$（$k\in Z$）的位置都是“#”。用一个桶来存模$m$后必须是“#”的位置，剩下的任意选。若有$t$个数满足存在一个$i$满足$i\%m=t$，那剩下的可以选“#”或“.”，也就是说取当前这个$m$值的满足题意的方案有$2^{m-t}$个。

当然，这样算会算重，比如算$m=2a$时有一部分是$m=a$时算过的。那么，我们记$p{t}_i$表示$n$的第$i$个约数$p_i$对答案的贡献，其中不包括$p_i$的不等于$p_i$的约数的贡献。那么，枚举$p_i$的不等于$p_i$的约数，用前面的$2^{m-t}$减去对应的$pt$值即可。

$n$的约数最多有$2\sqrt{n}$个，所以时间复杂度为$O(n\sqrt{n})$。

code

#include<bits/stdc++.h>
using namespace std;
int n,z[200005],p[200005],re[200005];
char s[100005];
long long ans=0,pt[200005];
const long long mod=998244353;
long long mi(long long t,long long v){if(!v) return 1;long long re=mi(t,v/2);re=re*re%mod;if(v&1) re=re*t%mod;return re;
}
int main()
{scanf("%d%s",&n,s+1);for(int i=1;i<n;i++){if(n%i==0){p[++p[0]]=i;re[i]=p[0];}}for(int i=1;i<=p[0];i++){for(int j=1;j<=n;j++){if(s[j]=='.') z[j%p[i]]=1;}int vt=p[i];for(int j=0;j<p[i];j++){if(z[j]){--vt;z[j]=0;}}pt[i]=mi(2,vt);for(int j=1;j<p[i];j++){if(p[i]%j==0){pt[i]=(pt[i]-pt[re[j]]+mod)%mod;}}ans=(ans+pt[i])%mod;}printf("%lld",ans);return 0;
}