Codeforces 93 D. Flags
問題
白、黒、赤、黄色の旗を一直線に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; }