ABC304F Shift Table
题目大意
小 T T T和小 A A A要做 n n n天的工作。
小 T T T的工作表表示为字符串 S S S,其中“#”表示当天要工作,“.”表示当天不需要工作。
你需要安排小 A A A的工作,步骤如下
- 选择一个 n n n的约数 m m m, m ≠ n m\neq n m=n
- 决定这 m m m天的工作安排
- 对于 i = 1 , 2 , … , n − m i=1,2,\dots,n-m i=1,2,…,n−m,第 i + m i+m i+m天的工作安排和第 i i i天的相同
求小 A A A有多少种工作安排,使得每一天都至少有一个人在工作?
输出答案模 998244353 998244353 998244353后的值。
2 ≤ n ≤ 1 0 5 2\leq n\leq 10^5 2≤n≤105
题解
首先,枚举 n n n的约数,即 m m m的值。然后,对于每一个为“.”的位置 i i i,小 A A A的这个位置都必须是“#”,所以小 A A A的所有 k × m + i k\times m+i k×m+i( k ∈ Z k\in Z k∈Z)的位置都是“#”。用一个桶来存模 m m m后必须是“#”的位置,剩下的任意选。若有 t t t个数满足存在一个 i i i满足 i % m = t i\% m=t i%m=t,那剩下的可以选“#”或“.”,也就是说取当前这个 m m m值的满足题意的方案有 2 m − t 2^{m-t} 2m−t个。
当然,这样算会算重,比如算 m = 2 a m=2a m=2a时有一部分是 m = a m=a m=a时算过的。那么,我们记 p t i pt_i pti表示 n n n的第 i i i个约数 p i p_i pi对答案的贡献,其中不包括 p i p_i pi的不等于 p i p_i pi的约数的贡献。那么,枚举 p i p_i pi的不等于 p i p_i pi的约数,用前面的 2 m − t 2^{m-t} 2m−t减去对应的 p t pt pt值即可。
n n n的约数最多有 2 n 2\sqrt n 2n个,所以时间复杂度为 O ( n n ) O(n\sqrt n) O(nn)。
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;
}