ABC304 F - Shift Table

執筆時レート：水色

問題文→https://atcoder.jp/contests/abc304/tasks/abc304_f
公式解説→https://atcoder.jp/contests/abc304/editorial/6511

目次

• 問題
• 制約
• 方針
• 計算量
• 実装

問題

高橋君と青木君は 日間アルバイトをする．
高橋君のシフト表は文字列 で与えられ， が#ならば 日目に出勤，. ならば 日目に欠勤する．
一方，青木君は以下の手順でシフト表を作成する．

• でない の正の約数 をとる．
• 日目から 日目までの勤怠を決める．
• の順に 日目の勤怠が 日目の勤怠と一致するように 日目の勤怠を決める．

※ の値が異なる場合でも最終的なシフトが等しくなる場合があることに注意．
日すべてについて高橋君と青木君の少なくとも一方が出勤することになったとき，青木君のシフト表として考えられるものの個数を で割ったあまりを求めよ．

制約

• は 以上 以下の整数
• は長さ の#, .からなる文字列

方針

サンプルケース1で考えてみる．

• 
• ##.#.#

青木君のシフト表を とする．
で考えてみる．
高橋君が欠勤する日は青木君は必ず出勤しなければならないので，最初の 日間のうち何日かは出勤で確定する(?は出勤か欠勤か選べる)．

• ?##

よって の場合では で 通り！
同じように他の でも求めて合計すればOK！
としたいところだが，?を#にしたときの ######は，
でも生成でき，重複して計上してしまう．

問題は重複をどう排除するか？になる．

このようなとき，(多分)2通りの考え方がある．

1. パターンと1対1対応するものを数える
2. とりあえず重複を区別して数えてからダブりを引く

1.は今回だとTの最小周期の文字列に対応させるという考え方．
例えば ######の最小周期は#なのでこれだけを直接数えるように頑張る．
でもムズカシイ．

2.は， を全探索してどこかのタイミングでダブりを引く．
を固定したとき，重複を区別すると というのは簡単．
どのようにしてダブりを引くか？

######を計上するのは1.と同じように最小周期で数えるとして， がそれ以外の周期のときでは計上しないようにしたい．

と固定して考える．
.##.##のような，「 が最小周期である場合」はここで初めて計上する．
一方，######のような，「 が最小周期でない場合」は， が最小周期のときに計上してるはずなので，ここでは計上しないようにする．

では「 が最小周期でない場合」を引くために，最小周期と の関係について調べてみる．

最小周期を とすると弱周期性補題より も周期．
であり， と仮定すると が最小周期であることに矛盾するので，． よって は の約数である．

つまり，「最小周期 でない の約数」が成立する．

よって，各 では「 が最小周期である場合」を計上しているので，ある が最小周期である場合の数は，

• 

で求められる． が小さい方から全探索すればよい．

計算量

の約数の個数を とする．
各 について，?の個数を数えるのに ，ダブりを引くのに かかるので，結局 かかる．
よって，最終的な計算量は となる．
今回の制約( )では，Nの約数の個数は高々128個なので十分高速である．

実装

https://atcoder.jp/contests/abc304/submissions/41989568

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)

/* Modint構造体(省略) */

// 約数列挙
vector<ll> divisor(ll n){
  vector<ll> ret;
  for(ll i=1;i*i<=n;i++){
    if(n%i==0) {
      ret.push_back(i);
      if(i!=n/i) ret.push_back(n/i);
    }
  }
  sort(ret.begin(),ret.end());
  return ret;
}
 
int main(){
  int n;cin>>n;
  string s;cin>>s;
 
  // nの約数列挙
  auto divs=divisor(n);
 
  // rem[i]:=最小周期がiである場合の数
  vector<mint> rem(n+1);
  // p2[i]:=2のi乗
  vector<mint> p2(n+1);
  p2[0]=1;
  rep(i,n) p2[i+1]=p2[i]*2;
  
  for(auto m:divs){
    if(m==n) continue;
 
    // 出勤/欠勤を選べる日数を数える
    int cnt=0;
    vector<bool> must(m);
    rep(i,n) {
      if(s[i]=='.'){
        must[i%m]=true;
      }
    }
    rep(i,m) if(!must[i]) cnt++;
 
    // 重複を区別した場合の数
    rem[m]=p2[cnt];
 
    // ここからダブりを引く
    for(int i=1;i<m;i++){
      if(m%i==0){
        rem[m]-=rem[i];
      }
    }
 
  }
 
  // remの合計が答え
  mint res=0;
  for(auto r:rem) res+=r;
 
  cout<< res <<'\n';
 
  return 0;
}