n度あることはn+1度ある

書きたいことを書く 統一性はない

ABC113 D - Number of Amidakuji

こちらに詳細を書きます。解法はDPです。データ構造はdp[i][j]で、問題の画像でいうところの、ind rowでjにたどり着ける場合の数です。
例えば以下の画像でj=1の線にいるとします。ここで、このポイントから移動できるのは、1から2へ線を引いた時のj=2と、1から0へ線を引いた時のj=0、そしてこの2つの線をどちらも引かなった場合のj=1です。
f:id:benntann:20181105174112p:plain
基本的にはこのパターンで、dp[i-1][j]の場合の数をdp[i][j-1],dp[i][j+1],dp[i][j]にコピーすればよいです。
しかし、他にも線を引けるところが残っている場合、線を引くパターン分だけ乗算する必要があります。 以下の画像では、矢印の移動を行ったとき、他に線を引くことができる箇所を同じ色の四角で示しています。
f:id:benntann:20181105174751p:plain
線を引く場合、線が隣り合わないことが条件なのですが、どのように引ける数のパターンを計算するかというと、線を引く時を1、引かない時を0とした二進数と考えるといいです。
最大のパターンがw=8のとき、0もしくは7の線にいるときに移動しないときの26です。しかし1が連続するbitは存在できないので、実際にはもっと少ないです。そのため計算してしまえば良いです。
もう線を引く場所がないときは、i-1番目のjをそのまま持ってくるので1パターン
1つ線を引く場所があるときは、0と1の2パターン
2つ線を引く場所があるときは、00、01、10の3パターン
3つ線を引く場所があるときは、000、001、010、100、101の5パターン
とみていくと結果として、0から6まで1,2,3,5,8,13,21となります。つまりこれらを掛けただけ増やすことができます。
よく見るとこれは漸化式でa1=1,a2=2,ai=a(i-1)+a(i-2)と表せます。そのためwが8より大きな制約でもこれを解くことができます。なぜこの漸化式になるのかはbitの生成パターンを見ればわかると思いますので、考えてみてください。
あとは移動する線を引いた後、左にいくつ線が引けるのか、右にいくつ線が引けるのかを確かめ、それぞれの場合の数を求めるだけです。
例えば上の画像の左から3番目にいるときを考えます。
左に移動しようとすると、赤い四角で囲ってあるように、移動する線より右側に2つ線が引けますので、
dp[i][4]+=dp[i-1][3]*3
右に移動しようとすると、右側に1つ、左側に1つそれぞれ線が引けますので、
dp[i][2]+=dp[i-1][3]*(2*2)
どこにも移動しないようにすると、右側に2つ、左側に1つそれぞれ線が引けますので、
dp[i][3]+=dp[i-1][3]*(3*2)
このようにDPを行っていきます。
そして最後のdp[h][w](自分のプログラムではdp[h][w-1])に結果が出てきます。

#include <bits/stdc++.h>
using namespace std;
#define INF 1000000007
int main(){
    int h,w,k; cin>>h>>w>>k;
    vector<vector<long>> dp(h+1,vector<long>(w,0));
    dp[0][0]=1;
    int num[]={1,2,3,5,8,13,21};
    for(int i=1;i<=h;i++){
        for(int j=0;j<w;j++){
            int l=j-1,r=w-1-(j+1);
            if(l<0)
                l=0;
            if(r<0)
                r=0;
            int a=num[r];
            if(l-1>=0)
                a*=num[l-1];
            int b=num[l];
            if(r-1>=0)
                b*=num[r-1];
            if(j-1>=0)
                dp[i][j-1]+=(dp[i-1][j]*a)%INF;
            if(j+1<w)
                dp[i][j+1]+=(dp[i-1][j]*b)%INF;
            int n=num[r]*num[l];
            dp[i][j]+=(dp[i-1][j]*n)%INF;
        }
    }
    cout<<dp[h][k-1]%INF;
}

因みに上記のような剰余を行うとDPを保存する配列をintにした場合途中でオーバーフローしました。