题解：AT_abc304_f [ABC304F] Shift Table

xiaolongmei · 2025-01-20 17:10:57 · 题解

题目传送门

题目大意

高桥和青木将在接下来的 N 天兼职工作。

高桥的轮班时间表由字符串 S 给出，其中，如果他在 i 天工作，则 S 的第 i 个字符为 #，如果他在 i 天缺勤，则为 .。

基于此，Aoki 创建了他的轮班时间表，如下所示。

• 首先，取 N 的正除数 M，该除数不等于 N。
• 接下来，确定前 M 天的出勤率。
• 最后，按照此顺序，对于 i = 1, 2, \ldots, N - M，确定第 (M + i) 天的出勤率，使其与第 i 天的出勤率相匹配。

请注意，不同的 M 值可能会导致相同的最终轮班安排。

找出青木可能的轮班安排数量，使得 高桥和青木中至少有一人在 N 天的每一天工作，模数为 998244353。

思路

很明显如果高桥第 i 天没工作，那么青木第 i 天就只有一种情况（必须工作）；而如果高桥第 i 天工作了，那么青木第 i 天就有两种情况（工作或者不工作），所以我们只需要遍历找 m，如果有高桥没工作的，答案乘以 2。

但是这样我们又会发现一个问题：当遍历的循环节为倍数关系时（如：2, 4, 8,\ldots）那么就会有重复计算部分，这种我们就需要用一个数组记录重复部分，在必要时候减去重复部分，然后就 OK 啦！

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=200005,m=998244353;
ll n,ans,v[N],c,f;/*c用来存储计算过程中可能的组合数 f用来判断某天是否需要工作 通过数组v[i]来防止重复计算*/
string s;
int main(){
    cin>>n>>s,s=" "+s;/*使s下标从1开始*/
    for(int i=1;i<n;i++){/*遍历找m*/
        if(n%i==0){/*找到符合条件m*/
            c=1;
            for(int j=1;j<=i;j++){/*以i为循环节遍历每天是否需要值班*/
                f=0;
                for(int k=j;k<=n;k+=i)if(s[k]=='.'){f=1;break;}/*如果高桥这天没值班青木这天必须值班*/
                if(f==0)c=(c*2)%m;/*方案数X2(01值班或不值)*/
            }
            ans=(ans+c-v[i]+m)%m;/*计算答案,-v[i]去重 +m防止ans<0*/
            for(int j=i+i;j<=n;j+=i)v[j]=(v[j]+c-v[i]+m)%m;/*去重数组i的倍数值刷新 +m同上*/
        }
    }
    cout<<ans;
    return 0;
}