ABC113 D - Number of Amidakuji
2020/3/8
https://gyazo.com/6b141fc1805f67ea1c83c0ad7adc032e
K番目の棒にいく場合の数を求めよ
方針
DPする
dp[i][j]: 交差点i行j列に辿り着く方法の場合の数
よくある経路DP
dp[0][0] = 1で初期化
i + 1行目の横棒の状態をbitで表現し、右か左に遷移できるなら遷移させる
ルールとして横棒が二つ以上繋がってはいけないので、その状態はパスする
code:cpp
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i) #define rep1(i,N) for(int i=1;i<int(N);++i) #define all(a) (a).begin(),(a).end() #define dump(x) cerr<<#x<<": "<<x<<endl; typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
const int INF = (ll)1e9;
const ll INFLL = (ll)1e18+1;
const ll MOD = (ll)1e9+7;
const double PI = acos(-1.0);
/*
const int dx8 = {1, 0, -1, 0, 1, -1, -1, 1}; const int dy8 = {0, 1, 0, -1, 1, 1, -1, -1}; const string dir = "DRUL";
*/
struct mint {
long long x; // typedef long long long long;
mint(long long _x=0):x((_x%MOD+MOD)%MOD){}
mint operator-() const { return mint(-x);}
mint& operator+=(const mint a) {
if ((x += a.x) >= MOD) x -= MOD;
return *this;
}
mint& operator-=(const mint a) {
if ((x += MOD-a.x) >= MOD) x -= MOD;
return *this;
}
mint& operator*=(const mint a) {
(x *= a.x) %= MOD;
return *this;
}
mint operator+(const mint a) const {
mint res(*this);
return res+=a;
}
mint operator-(const mint a) const {
mint res(*this);
return res-=a;
}
mint operator*(const mint a) const {
mint res(*this);
return res*=a;
}
mint modpow(long long t) const {
if (!t) return 1;
mint a = modpow(t>>1);
a *= a;
if (t&1) a *= *this;
return a;
}
// for prime MOD
mint inv() const {
return modpow(MOD-2);
}
mint& operator/=(const mint a) {
return (*this) *= a.inv();
}
mint operator/(const mint a) const {
mint res(*this);
return res/=a;
}
};
int H,W,K;
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
cout << fixed << setprecision(20);
//横移動がH回まで
cin>>H>>W>>K;
K--;
//j: [0, W)
rep(i,H)rep(j,W){
//i行目のあみだくじの状態をbit全探索
for(int k = 0; k < bit(W-1);k++){
bool ok = true;
//隣り合っているかの確認
for(int l = 0; l < W - 2;l++){
if((k & bit(l)) && (k & bit(l+1)))ok = false;
}
if(!ok)continue;
int nj = j;
if(k & bit(j))nj = j+1;
else if(j > 0 && (k & bit(j - 1)))nj = j-1;
}
}
}