D - Number of Amidakuji
問題
考えていたこと
・まではすぐにたどりつけたが、「正しいあみだくじ」の本数を求める方法がわからず。
・からに推移できる。
解法
・番目にいるときの、あり得るあみだくじの場合の数を計算する。
・当たり前だけど、あみだくじの状態が決まれば推移先は一つに決まる。(条件が厳しくなっている。)
・なんちゃってdynamic_bitsetを作りました。
#include<bits/stdc++.h> using ll = long long; #define int ll #define rep(i,n) for(int i=0;i<n;i++) using namespace std; template<typename Head, typename Value> auto vectors(const Head &head, const Value &v) { return vector<Value>(head, v); } template<typename Head, typename... Tail> auto vectors(Head x, Tail... tail) { auto inner = vectors(tail...); return vector<decltype(inner)>(x, inner); } int MOD = 1000000007; class dynamic_bitset { private: long long bit; string sbit = ""; unsigned long long bitsize = 0; public: dynamic_bitset(int _bit) : bit{_bit} { for (int t = 1, mask = 2; bitsize == 0; t++, mask *= 2) { if (mask - 1 >= bit) bitsize = t; } for (int i = 0; i < bitsize; i++) { sbit = ((bit >> i & 1) == 1 ? "1" : "0") + sbit; } } dynamic_bitset(int _bit, int bitrange) : bit{_bit}, sbit{} { for (int t = 1, mask = 2; bitsize == 0; t++, mask *= 2) { if (mask - 1 >= bit) bitsize = t; } for (int i = 0; i < bitrange; i++) { sbit = (i < bitsize and ((bit >> i & 1) == 1) ? "1" : "0") + sbit; } } auto test(int _idx) { assert(_idx < sbit.size() && "index out of range"); return sbit[_idx] == '1'; } void set(int _idx) { assert(_idx < sbit.size() && "findex out of range"); sbit[_idx] = '1'; } auto size() { return sbit.size(); } bool isAll() { return accumulate(sbit.begin(), sbit.end(), true, [](bool r, char c) { return r && c == '1'; }); } bool none() { return accumulate(sbit.begin(), sbit.end(), true, [](bool r, char c) { return r && c == '0'; }); } auto to_string() { return sbit; } }; signed main(){ int h,w,k; cin >> h >> w >> k; auto dp = vectors(300, 300,0LL); dp[1][1] = 1; for(int j = 1; j <= h; j++){ for(int i = 1; i <= w; i++){ for(int bit = 0; bit < (1 << (w - 1));bit++){ auto db = dynamic_bitset(bit,w-1); bool isValid = true; rep(i,(int)db.size() - 1){ if(db.test(i) and db.test(i+1)) isValid = false; } if(!isValid)continue; if(i+1 <= w and db.test(i-1)){ dp[i+1][j+1] = (dp[i+1][j+1] + dp[i][j]) % MOD; } else if(i-1 >= 1 and db.test(i-2)){ dp[i-1][j+1] = (dp[i-1][j+1] + dp[i][j]) % MOD; } else { dp[i][j+1] = (dp[i][j+1] + dp[i][j]) % MOD; } } } } cout << dp[k][h+1] << endl; }