メモ化する。
memo[ 使った 0 の数 ][ 使った 1 の数 ]
0 と 1 はそれぞれ先頭から使う。つまり、入れ替わりが発生するのは同じ数同士ではない。
与えられた遅延の値を見ていけば答えは出せる。
#include <algorithm> #include <iostream> #include <map> #include <numeric> #include <queue> #include <set> #include <stack> #include <vector> #include <sstream> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <cassert> #define REP(i, n) for(int i=0; i<(int)n; ++i) #define FOR(i, c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i) #define ALL(c) (c).begin(),(c).end() #define each(i, c) FOR(i, c) #define VAR(a) cout << #a << " : " << a << endl; typedef long long int lli; typedef unsigned long long int ulli; using namespace std; const int ONE = 64 + 1; const int ZERO = 64 + 1; ulli memo[ONE][ZERO]; bool vis[ONE][ZERO]; int size_o, size_z; int D; lli O[ONE], Z[ZERO]; ulli rec(int o, int z) { if (vis[o][z]) return memo[o][z]; vis[o][z] = true; if (o == size_o && z == size_z) return memo[o][z] = 1; ulli sum = 0; int curr = max(O[o - 1], Z[z - 1]); bool prev; bool next; prev = next = false; if (O[o] < curr && O[o] + D >= curr) { prev = true; } if (curr <= O[o]) { next = true; } if (o < size_o && (prev || next)) { sum += rec(o + 1, z); } prev = next = false; if (Z[z] < curr && Z[z] + D >= curr) { prev = true; } if (curr <= Z[z]) { next = true; } if (z < size_z && (prev || next)) { sum += rec(o, z + 1); } return memo[o][z] = sum; } ulli conv(string s) { ulli n = 0; reverse(s.begin(), s.end()); for (ulli i = 0; i < (ulli)s.size(); ++i) { if (s[i] == '1') { n |= (ulli)1 << i; } } return n; } string ulli2s(int len, ulli num) { string s = ""; for (int i = 0; i < len; ++i) { s += '0' + (num % 2LL); num /= (ulli)2; } reverse(s.begin(), s.end()); return s; } ulli make_max(int len, ulli num) { string s = ulli2s(len, num); vector< pair<int, int> > v; for (int i = 0; i < (int)s.size(); ++i) { if (s[i] == '1') v.push_back(make_pair(i, -1)); else v.push_back(make_pair(i + D, 0)); } sort(v.begin(), v.end()); for (int i = 0; i < (int)s.size(); ++i) { if (v[i].second == 0) { s[i] = '0'; } else { s[i] = '1'; } } return conv(s); } ulli make_min(int len, ulli num) { string s = ulli2s(len, num); vector< pair<int, int> > v; for (int i = 0; i < (int)s.size(); ++i) { if (s[i] == '1') v.push_back(make_pair(i + D, 1)); else v.push_back(make_pair(i, 0)); } sort(v.begin(), v.end()); for (int i = 0; i < (int)s.size(); ++i) { if (v[i].second == 0) { s[i] = '0'; } else { s[i] = '1'; } } return conv(s); } int main(int argc, char *argv[]) { ulli n, k; while (cin >> n >> D >> k) { size_o = size_z = 0; O[size_o++] = 0; Z[size_z++] = 0; for (lli i = n - 1; 0 <= i; --i) { if (k & (1LL << i)) O[size_o++] = n - i - 1; else Z[size_z++] = n - i - 1; } fill(&vis[0][0], &vis[ONE - 1][ZERO], false); ulli mem = rec(1, 1); ulli mn = make_min(n, k); ulli mx = make_max(n, k); static int tc = 0; cout << "Case " << ++tc << ": " << mem << ' ' << mn << ' ' << mx << endl; } return 0; }