一、题目描述：
给你一个长度为 $n$ 的字符串 $s$ ，$s_i$ 要么是 $\#$ ，要么是 $.$ 。
求有多少种长度为 $n$ 的字符串 $t$ ，恰好由一个长度为 $\frac{n}{x}$ 的字符串循环 $x$ 次得来,
且对于每一个 $i$ 使得 $s_i$ 为 $.$，$t_i$ 为 $\#$。答案对 $998244535$ 取模。
数据范围：$1\leq n\leq 1\times 10^5$ 。
二、解题思路：
枚举每一个 $n$ 的因数，单独进行计算。
如果存在 $i|j$ ，显然在计算 $j$ 的时候会重复计算 $i$ 。
每一次暴力减去重复计算的部分即可。时间复杂度 $O(n \sqrt {n})$。
三、完整代码：
1 #include<iostream>
2 #include<algorithm> 3 #define ll long long 4 #define mod 998244353 5 #define N 100010 6 using namespace std; 7 bool p[N]; 8 string str; 9 ll n,cc,cnt,ans,now; 10 ll a[N],p2[N],res[N]; 11 void solve(int m) 12 { 13 for(int i=1;i<=m;i++) 14 p[i]=0;now=cnt=0; 15 for(int i=0;i<n;i++) 16 if(str[i]=='.') 17 p[i%m+1]=1; 18 for(int i=1;i<=m;i++) 19 cnt+=p[i]; 20 for(int i=1;i*i<=m;i++) 21 if(m%i==0) 22 { 23 (now-=res[i])%=mod; 24 if(i*i!=m)(now-=res[m/i])%=mod; 25 } 26 (now+=p2[m-cnt]+mod)%=mod; 27 (ans+=now)%=mod,res[m]=now; 28 } 29 int main() 30 { 31 ios::sync_with_stdio(0); 32 cin.tie(0),cout.tie(0); 33 cin>>n>>str,p2[0]=1; 34 for(int i=1;i<=n;i++) 35 p2[i]=p2[i-1]*2%mod; 36 for(int i=1;i*i<=n;i++) 37 if(n%i==0) 38 { 39 a[++cc]=i; 40 if(i*i!=n&&i!=1) a[++cc]=n/i; 41 } 42 sort(a+1,a+1+cc); 43 for(int i=1;i<=cc;i++) 44 solve(a[i]); 45 cout<<ans<<'\n'; 46 return 0; 47 }
四、写题心得：
这样一写好像这个题非常简单，但实际上赛时因为没有考虑到一个数可能会被减多次而 $WA$ 了。
不过比赛已经 $Unrated$ 了，所以也没什么影响。(可恶 $Atcoder$ 评测机为什么会卡啊喂$qwq$ !)。
加油吧！拜拜！