Codeforces 93 D. Flags

Codeforces 確率・場合の数

問題

白、黒、赤、黄色の旗を一直線にL個以上R個以下並べる。
次の条件を満たす並べ方はいくつあるか、mod 10^9+7で求めよ。

  • 同じ色が連続しない
  • 白と黄色が並ばない
  • 黒と赤が並ばない
  • 黒白赤がこの順または、この逆順に並ばない

ただし、左右反転させて重なるものはひとつと数えることにする。

制約条件

L,R≦10^9

方針

遷移行列を作って繰り返し二乗法。
状態は、直前の2個の旗の色を組にしたもの。


まずは対称性を無視して考える。
求めたいのは、f(L)+f(L+1)+……+f(R)であるので、
まずは行列の和 E + M + M^2 + … M^n を求めたい。
これは蟻本p184にもあるように、

M O
I I

という行列を作って、それをk乗すればよい。


次に対称性のある形をひとつと数えることを考える。
旗の数が偶数のとき、どの並べ方にも左右反転させた並べ方1通りが対応するので、2で割ればよい。
旗の数が奇数のときは、旗が(n+1)/2個の並べ方に等しい数の並べ方が1度だけ数えられていて、他の並べ方は2度数えられているので、f((n+1)/2)を足して2で割ればよい。


これを和で考えると、
( f(n)+f(n-1)+f(1)-f((n+1)/2)-f((n+1)/2-1)-…f(2) )/2という形をすることがわかるので、
求めるのは、( Σf(n)-Σf((n+1)/2)+f(1)+f(0) )/2である。

ソースコード

typedef vector<vi> mat;
const int mod=(int)1e9+7;

mat operator*(const mat &a,const mat &b){
  mat res(a.size(),vi(b[0].size()));
  assert(a[0].size()==b.size());
  rep(i,res.size())rep(j,res[0].size())rep(k,a[0].size()){
    res[i][j]+=a[i][k]*(ll)b[k][j]%mod;
    res[i][j]%=mod;
  }
  return res;
}
mat pow(mat m,int n){
  mat res(m.size(),vi(m.size()));
  rep(i,m.size())res[i][i]=1;
  for(;n;n>>=1){
    if(n&1)res=res*m;
    m=m*m;
  }
  return res;
}
int solve(int n){
  mat M(25*2,vi(25*2));
  rep(i,5)rep(j,5){
    for(int k=1;k<5;k++){
      if(j==k||j==1&&k==4||j==4&&k==1||
      j==2&&k==3||j==3&&k==2||
      i==2&&j==1&&k==3||i==3&&j==1&&k==2)continue;
      M[k*5+j][j*5+i]=1;
    }
  }
  rep(i,25)M[i+25][i]=M[i+25][i+25]=1;
  M=pow(M,n+1);
  mat A(50,vi(25));
  rep(i,25)A[i][i]=1;
  mat B=M*A;
  mat C(25,vi(1));
  C[0][0]=1;
  mat D=B*C;
  ll res=0;
  rep(i,25)res+=D[i+25][0];
  return res%mod;
}
int calc(int n){
  int res=((ll)solve(n)+solve((n+1)/2)-solve(2)+mod)%mod;
  if(res%2)res+=mod;
  res/=2;
  return res;
}
void run(){
  int l,r;
  cin>>l>>r;
  ll ans=calc(r)-calc(l-1);
  ans=(ans%mod+mod)%mod;
  cout<<ans<<endl;
}