Codeforces #191 Div2 E "Axis Walking"
チュートリアルを見て
よくわからん。
O(2^N * N)はだめ!O(3^(N/2) * N^2)がいいって言ってるけど、4億と3億であんまり違いが無いような・・・。それに、後者のほうは1つ1つの処理が重いから結局前者のほうが速かったというね。
うーん・・・。
結局ビットDPで通す。
ソースコード
const int MOD = 1000000007; int n; int k; int k1, k2; long long a[1<<24]; long long s[1<<24]; int dp[1<<24]; int main() { // 入力 cin >> n; for( int i = 0; i < n; i++ ){ cin >> a[1<<i]; } k1 = k2 = -1; cin >> k; if( k == 1 ){ cin >> k1; }else if( k == 2 ){ cin >> k1 >> k2; } // dp初期化 memset( dp, 0, sizeof(dp) ); dp[0] = 1; s[0] = 0; // dp更新 for( int b = 0; b < 1 << n; b++ ){ s[b] = s[b - (b & -b)] + a[b & -b]; if( s[b] == k1 || s[b] == k2 ) dp[b] = 0; if( dp[b] == 0 ) continue; for( int i = 0; i < n; i++ ){ int m = 1 << i; if( b & m ) continue; int nb = b | m; dp[nb] = dp[nb] + dp[b]; if( dp[nb] > MOD ) dp[nb] -= MOD; } } cout << dp[(1<<n)-1] << endl; }