ARC193 B. Broken Wheel

Difficulty:2420

問題

N+1頂点のグラフがある。頂点0からN-1は、頂点i+1とつながっている（N-1は0と）。

文字列Sのi文字目が1のとき、頂点Nと頂点iがつながっている。

このグラフに向きをつけたときにできる入次数の配列の種類数を数え上げよ。

解法

dp[i][j] = i番目の辺まで向きを決めて、最後の向きでありそうなものがjになっているときの数列の種類数

左向き、右向き、どちらもあるの3通りの添え字を持って、3回DPする。

重複が発生するので2を引く。

実装

code:cpp

bool solve(){

LL(n);

STR(s);

mint ans{-2};

vector dp(n+1,vector(3,mint(0)));

rep(i,n){

//Di == 2

//Di == 0

//Di == 1

//Di == 3

//Di == 2

//Di == 1

}

else{

}

}

};

rep(ii,3){

f();

}

O(ans.val());

return true;

}