题解：AT_abc304_f [ABC304F] Shift Table

思路

首先，很容易想到枚举合法的循环节长度，然后遍历整个字符串，对必须要干活的天数进行标记，最后记循环节长度为 \(l\)，标记天数为 \(cnt\)，则这个循环节长度就有 \(2^{l-cnt}\) 个合法方案。

但是这样计算会导致部分部分方案重复计算，比如所有天数都干活的方案在所有循环节长度都被计算了一次。我们思考一下重复计算的原因，显然如果我们在枚举一个小的循环节长度时，找到了一个合法的方案，那么在枚举该长度的整数倍时这个方案都会被计算，尽管它们是同一种。

所以最后计算方法是：先将 \(n\) 除了它自己以外的所有因数从小到大排序，依次处理，每次先计算出 \(2^{l-cnt}\)，然后减去以该循环节长度因数为循环节长度的方案数，得到当前循环节长度的真实方案数，然后再计算答案和进行容斥。

代码

#include<bits/stdc++.h>
#define int long long
#define MAXN 100005
using namespace std;
const int inf=1e18,mod=998244353;
int n,ans,d[MAXN],cnt,b[MAXN],sum,f[MAXN],zcnt,ys[MAXN],ycnt,p[MAXN];
char c[MAXN];
int fpow(int a,int b){int tans=1;while(b){if(b&1)tans=tans*a%mod;a=a*a%mod;b>>=1;}return tans;
}
void solve(int x){sum=x;for(int i=1;i<=cnt;i++){if(!b[d[i]%x])sum--;//对必须要干活的天数进行标记b[d[i]%x]++;}int tmp=p[sum];//计算2^(l-cnt)tmp=(tmp+mod-f[x])%mod;//减去重复方案for(int i=1;x*i<=n;i++){f[x*i]=(f[x*i]+tmp)%mod;//更新倍数的容斥}ans=(ans+tmp)%mod;//计算答案for(int i=1;i<=cnt;i++){b[d[i]%x]=0;}
} 
signed main(){
//	freopen("clr.in","r",stdin);
//	freopen("clr.out","w",stdout);scanf("%lld",&n);p[0]=1;for(int i=1;i<=n;i++)p[i]=p[i-1]*2%mod;scanf("%s",c+1);for(int i=1;i<=n;i++)if(c[i]=='.')d[++cnt]=i;for(int i=1;i*i<=n;i++){if(n%i==0){ys[++ycnt]=i;if(i*i!=n&&i!=1)ys[++ycnt]=n/i;}}sort(ys+1,ys+ycnt+1);//n的因数从小到大排序依次处理for(int i=1;i<=ycnt;i++){solve(ys[i]);}printf("%lld\n",ans);return 0;
}