Codeforces 107 D. Crime Management

問題

文字列に対しての条件がc個与えられる。

• アルファベットa[i]がちょうどw[i]の整数倍個だけ含まれている
• ただし、同じアルファベットに対してw[i]が複数個定義されている場合、w[i]のどれかの倍数になっていればよい。

長さnの文字列で条件を満たすものの個数をmod 12345で求めよ。
条件に一度も現れていないアルファベットは1回も使ってはならないものとする。

制約条件

n≦10^18
c≦1000
w[i]の全ての積≦123

方針

長さnの時にそれぞれのアルファベットのw[i]の余りがr[i]であるときの場合の数を求めたい。
これは、c個の余りを1つの整数にコーディングすれば、w[i]の全ての積が123以下であることから、123以下の整数として表せる。

新たに末尾に一文字を加えるときに、r[i]がどのように遷移するかを行列として表せば、
長さnの場合の数が行列のn乗として表せることになる。
行列のn乗を繰り返し二乗法により求めた後、余りが全て条件を満たしている成分を足し合わせれば、答えの場合の数が求まる。

ソースコード

const int mod=12345;
mat operator*(const mat &a,const mat &b){
  mat res(a.size(),vi(b[0].size()));
  rep(i,res.size())rep(j,res[0].size())rep(k,a[0].size())(res[i][j]+=a[i][k]*b[k][j])%=mod;
  return res;
}
mat pow(mat m,ll n){
  mat res(m.size(),vi(m.size()));
  rep(i,res.size())res[i][i]=1;
  for(;n;n>>=1){
    if(n&1)res=res*m;
    m=m*m;
  }
  return res;
}

void run(){
  ll n;
  int c;
  cin>>n>>c;
  vi v[26];
  int szs[26];
  rep(i,c){
    char a; int m;
    cin>>a>>m;
    v[a-'A'].pb(m);
  }
  int sz=1;
  rep(i,26){
    int lcm=1;
    rep(j,v[i].size())lcm=lcm*v[i][j]/__gcd(lcm,v[i][j]);
    sz*=lcm;
    szs[i]=lcm;
  }
  mat M(sz,vi(sz));
  rep(i,sz){
    vi nums; int m=i;
    rep(j,26){
      nums.pb(m%szs[j]);
      m/=szs[j];
    }
    rep(j,26){
      vi nxt=nums;
      nxt[j]=(nxt[j]+1)%szs[j];
      int m=0;
      for(int k=25;k>=0;k--)m=m*szs[k]+nxt[k];
      if(!v[j].empty())M[m][i]++;
    }
  }
  M=pow(M,n);
  int ans=0;
  rep(i,sz){
    vi nums; int m=i;
    bool ok=1;
    rep(j,26){
      nums.pb(m%szs[j]);
      m/=szs[j];
      bool ok2=v[j].empty();
      rep(k,v[j].size())if(nums[j]%v[j][k]==0)ok2=1;
      if(!ok2)ok=0;
    }
    if(ok)ans+=M[i][0];
  }
  cout<<ans%mod<<endl;
}