2019-2020 ICPC Brazil Subregional K- Keep Calm and Sell Balloons

これのK問題を解いたので、解法のメモを残します。

問題概要

2*Nのグリッドが与えられ、好きな点を一つ選びそこから縦横斜めに隣接する一つのマスを選んで移動する、ただし同じ頂点は二度通ることができない。この時全てのマスを丁度一回通るような移動の総数を で割った余りを求めよ。

制約

解法

まずは部分問題として、次の二つの総数を数式で表すことを考えます。

1. 2*Nのグリッドの左上からスタートして、終点が任意の位置にある場合の総数（これを とおきます）
2. 2*Nのグリッドの左上からスタートして、終点が始点の下の点となる総数（これを とおきます）

2つ目から考えていきます。お絵かきをします。

このように同じ列で縦方向の移動をするとグリッドが分断されて戻れなくなってしまうことを考えると、N-1個の列において始めに上と下どちらを先に選ぶか、を決めると一筆描きの経路は一意に定まります。

よって  と表す事が出来ます(n=1でも成立)

続いて についても考えていきます。

の一般項を求めるに当たって以下の場合分けをします。

• 始めに下に進む場合

この時、次に進むマスとして上下の二択が考えられるが、どちらに進んでもこれは2*(n-1)のグリッドの左上から任意終点へ一筆描きする経路の総数に一致するため と表す事が出来ます。

• 始めに右上または右下に進む場合

先ほどの数列 で考えられていないのはどのような場合でしょうか。

こういう場合です。

1,2それぞれの場合において次に移動するマスの上下を選ぶ事ができて、また移動先の場合は の場合に帰着しています。

以上の考察から、 の一般項は と表す事が出来ます。(初項はと定義します)

次に求める一筆描きの経路の総数を求めていきたいと思います。

N=1の時は2を出力することにして、以下 で議論します。

グリッドの4つの角のマスは上で考えた がそのまま適用できるので、 と表す事が出来ます。

上側の角のマスではないところを始点とした経路の総数を とすると、上下の対称性より となります。

ざっくり説明すると、真ん中のマスから始めるとグリッドの分断をしない為に左→右or右→左の移動をする必要があり、初めの移動は で次の移動は で表せることに留意すると

左右の対称性を考えて、

と の関係性を考えた時に の項に注目すると、 となることが分かり、残りの項の係数を考慮すると となることが分かります。(初項は で定義します)

ここまで来るともうゴールは近いです。

上記の漸化式は行列の式で表す事が出来ます。

あとはこれを行列累乗で計算することによって答えが得られます。

実装 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long int ll;

ll mod=1e9+7;

struct mat{
    ll x[4][4];
    friend mat operator*(mat &a,mat & b){
        mat c;
        for(int i=0;i<4;i++){
            for(int j=0;j<4;j++){
                c.x[i][j]=0;
                for(int k=0;k<4;k++){
                    (c.x[i][j]+=a.x[i][k]*b.x[k][j]%mod)%=mod;
                }
            }
        }
        return c;
    }
};

mat x={2,4,0,2,1,0,0,0,0,8,2,0,0,0,0,2};

mat modexp(mat x,mat ans,ll n){
    while(n){
        if(n%2)ans=x*ans;
        x=x*x;
        n/=2;
    }
    return ans;
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n; cin >> n;
    if(n==1){
        cout << 2 << endl;
        return 0;
    }
    mat ans;
    ans.x[0][0]=6,ans.x[1][0]=1,ans.x[2][0]=0,ans.x[3][0]=2;
    ans=modexp(x,ans,n-2);
    ll sum=4*ans.x[0][0]%mod+2*ans.x[2][0]%mod;
    sum%=mod;
    cout << sum << endl;
}