DP + 容斥
定义$f[i]$为选择$i$为周期的数量,$dp[i]$为长度为$i$的总数
考虑到重复计算,不能直接用$dp$(总数)来转移,应该用每一次的状态来记录总数
对于$dp[i]$来说,我们需要固定一些位置为’#’,其他的地方暴力计算$2^n$种选择
$dp[i] = \sum_1^if[j]$注意需要i % j = 0才能转移
$f[j] = dp[j] - \sum_1^{j-1}f[k]$
if(n % i == 0)
答案:$\sum_1^nf[i]$
C++ 代码
#include <iostream>
#include <vector>
using namespace std;
const int MOD = 998244353, N = 2e6 + 10;
using LL = long long;
int n;
string s;
int dp[N];
int qmi(int x, int y)
{
x %= MOD;
int res = 1;
while(y)
{
if(y & 1) res = (LL) res * x % MOD;
x = (LL) x * x % MOD;
y >>= 1;
}
return res;
}
int main()
{
cin >> n >> s;
for(int i = 1; i < n; i ++ )//找约数
{
if(n % i == 0)
{
vector<int> f(i, 1);//记录所有任意填的位置
for(int j = 0; j < n; j ++ )
if(s[j] == '.')
f[j % i] = 0;
LL cnt = 0;
for(int j = 0; j < i; j ++ ) cnt += f[j];
dp[i] = qmi(2, cnt);//2^cnt可以任意填
for(int j = 1; j < i; j ++ )
if(i % j == 0)
dp[i] = (dp[i] - dp[j] + MOD) % MOD;
}
}
int ans = 0;
for(int i = 1; i < n; i ++ ) ans = (ans + dp[i]) % MOD;
cout << ans << "\n";
return 0;
}