【校内训练2019-05-22】神秘代码

【思路要点】

注意到若序列中 $0$ 的限制不存在，我们便只需要将每一条链分成若干段，使得长度一定的段数量一定即可，可以设计一个简单的 $dp$ 解决问题。考虑容斥原理，枚举将 $0$ 的限制变为 $1$ 的限制。注意到最长的链 $1-2-4-8-16-32$ 长度为 $6$ ，因此我们只需要统计 $6$ 种长度的段的数量，实际状态数 $Cnt$ 为 $3692$ 。用 $dp$ 优化上述枚举的过程即可。时间复杂度 $O(6NCntLogCnt)$ 。

【代码】

#include<bits/stdc++.h> using namespace std; const int MAXN = 45; const int P = 1e9 + 7; typedef long long ll; typedef long double ld; typedef unsigned long long ull; template <typename T> void chkmax(T &x, T y) {x = max(x, y); } template <typename T> void chkmin(T &x, T y) {x = min(x, y); } template <typename T> void read(T &x) { x = 0; int f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = -f; for (; isdigit(c); c = getchar()) x = x * 10 + c - '0'; x *= f; } template <typename T> void write(T x) { if (x < 0) x = -x, putchar('-'); if (x > 9) write(x / 10); putchar(x % 10 + '0'); } template <typename T> void writeln(T x) { write(x); puts(""); } int n, fac[MAXN]; char s[MAXN]; map <vector <int>, int> mp[MAXN]; map <vector <int>, int> dp[MAXN]; void update(int &x, int y) { x += y; if (x >= P) x -= P; } void debug(vector <int> a) { for (auto x : a) cerr << x << ' '; cerr << endl; } int main() { freopen("code.in", "r", stdin); freopen("code.out", "w", stdout); read(n), scanf("\n%s", s + 1); vector <int> cipher; cipher.resize(7); mp[0][cipher] = 1; for (int i = 0; i <= n - 1; i++) { int coef = 1; for (int j = 1; j <= 6 && j <= n - i; j++) { if (j != 1 && s[i + j - 1] == '0') coef = P - coef; if (s[i + j] == '1') continue; for (auto x : mp[i]) { vector <int> tmp = x.first; tmp[j]++; update(mp[i + j][tmp], 1ll * coef * x.second % P); } } } fac[0] = 1; for (int i = 1; i <= n; i++) fac[i] = 1ll * fac[i - 1] * i % P; for (auto x : mp[n]) { int tmp = x.second; for (auto y : x.first) tmp = 1ll * tmp * fac[y] % P; dp[0][x.first] = tmp; } int tot = 0; for (int i = 1; i <= n; i += 2) { for (int j = 2 * i; j <= n; j *= 2) s[++tot] = '0'; s[++tot] = '1'; } for (int i = 0; i <= n - 1; i++) { for (int j = 1; j <= 6 && j <= n - i; j++) { int coef = 1 + (j != 1); for (auto x : dp[i]) { vector <int> tmp = x.first; if (--tmp[j] < 0) continue; update(dp[i + j][tmp], 1ll * coef * x.second % P); } if (s[i + j] == '1') break; } } writeln(dp[n][cipher]); return 0; }