TopCoder SRM 428 Div1 Medium TheLongPalindrome

問題

英小文字からなる、長さがn文字以下で、使われているアルファベットがk種類以下であるような回文の数をmod 1234567891で求めよ。

制約条件

n≦10^9
k≦26

方針

長さnの回文は、長さ(n+1)/2の文字列の数に等しい。
なので、アルファベットがk種類以下で、長さ(n+1)/2の文字列の総数をn=1からnまで求めればよい。

行列で求める。
列ベクトルF(n)を、i番目の成分が「長さnの文字列で、アルファベットがちょうどi文字だけ登場するようなものの総数」とする。
すると、
[0 26 0 …… 0 ]
[0 1 25 …… 0 ]
……
[0 0 0 …… 1 ]
[0 0 0 …… 26]
であるような行列Aを使って、
F(n+1)=F(n)*Aと表すことができる。

行列の累乗の和は蟻本にあるように、
[A O]
[I I]
の行列を累乗することで求めることができる。

ソースコード

const int mod=1234567891;
typedef vector<vi> mat;
mat operator*(mat &a,mat &b){
  mat c(a.size(),vi(b[0].size()));
  rep(i,c.size())rep(j,c[0].size())rep(k,a[0].size())
    (c[i][j]+=a[i][k]*b[k][j])%=mod;
  return c;
}
mat pow(mat a,int n){
  mat res(a.size(),vi(a[0].size()));
  rep(i,res.size())res[i][i]=1;
  for(;n;n/=2){
    if(n&1)res=res*a;
    a=a*a;
  }
  return res;
}
mat powsum(mat &a,int n){
  int m=a.size();
  mat b(2*m,vi(2*m));
  rep(i,m)rep(j,m)b[i][j]=a[i][j];
  rep(i,m)b[i+m][i]=b[i+m][i+m]=1;
  b=pow(b,n);
  mat res(m,vi(m));
  rep(i,m)rep(j,m)res[i][j]=b[i+m][j];
  return res;
}
ll calc(int n,int k){
  mat a(27,vi(27));
  rep(i,26)a[i+1][i+1]=i+1, a[i][i+1]=26-i;
  mat b=powsum(a,n); b=b*a;
  
  mat c(1,vi(27));
  c[0][0]=1;
  c=c*b;
  ll ans=0;
  rep(i,k)ans+=c[0][i+1];
  return ans%mod;
}

class TheLongPalindrome {
  public:
  int count(int n, int k) {
    return (calc(n/2,k)+calc((n+1)/2,k))%mod;
  }
};