题目传送门

题目大意

高桥和青木将在接下来的

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 啦！

代码

CPP

#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;
}

题解：AT_abc304_f [ABC304F] Shift Table

文章操作

题目传送门

题目大意

思路

代码

相关推荐

评论

题解：AT_abc304_f [ABC304F] Shift Table