- TJOI2015 棋盘
- PKUSC2018 最大前缀和
- NOI2015 寿司晚宴
- ZJOI2016 小星星
- JSOI2016 位运算
- THUWC2017 随机二分图
- PKUWC2018 随机算法
- JLOI2016 字符串覆盖
- USACO13JAN Island Travels G
- SDOI2009 学校食堂
上接 状压dp
G 题（LOJ #6495 树）那个题不是状压 DP 就不放了 . 状压专题里放一道不是状压的题是 HZ 传统吗？
TJOI2015 棋盘
校内 OJ 那个题面还得看样例才能猜出来 0-indexed，而且样例还不符合题意？？？
首先因为 0-indexed，所以其实是每个棋子可以打前面一行和后面一行，于是每次只需要记录 \(dp_{i,state}\) 表示到第 \(i\) 行目前状态是 \(state\)，然后枚举 \(i+1\) 行的状态 \(state'\)，然后拿 \(state\) 的攻击范围和 \(state'\) 的攻击范围互相判一下就行了 .
这么整就 \(\Theta(n2^{2m})\) 了，显然过不去，然而矩阵快速幂优化一下就 \(\Theta(2^{3m}\log n)\) 了，就能过了 .
Code
const int N = 70, INF = 0x3f3f3f3f;
int n, m, p, k, len;
int atk[3];
vi ok;
struct matrix
{
const static int n = 65;
u32 a[N][N];
matrix(char type = 'O'){memset(a, 0, sizeof a); if (type == 'I'){for (int i=0; i<=n; i++) a[i][i] = 1;}}
matrix operator * (const matrix& rhs)
{
matrix res;
for (int i=0; i<=n; i++)
for (int k=0; k<=n; k++)
for (int j=0; j<=n; j++) res[i][j] += a[i][k] * rhs[k][j];
return res;
}
matrix& operator *= (const matrix& rhs){return *this = *this * rhs;}
const u32* operator [](const u32& id) const {return a[id];}
u32* operator [](const u32& id){return a[id];}
}M;
matrix qpow(matrix a, ll n)
{
matrix ans('I');
while (n)
{
if (n & 1) ans *= a;
a *= a; n >>= 1;
} return ans;
}
inline int mov(int x, int p, int k){return (p <= k) ? (x << (k - p)) : (x >> (p - k));}
inline bool check(int x)
{
for (int i=0; i<32; i++)
if ((x & (1 << i)) && (x & mov(atk[1], p, i+k) & ((len-1) ^ (1<<i)))) return false;
return true;
}
inline bool check(int x, int y)
{
for (int i=0; i<m; i++)
if ((x & (1 << i)) && (y & mov(atk[2], p, i+k))) return false;
for (int i=0; i<m; i++)
if ((y & (1 << i)) && (x & mov(atk[0], p, i+k))) return false;
return true;
}
int main()
{
scanf("%d%d%d%d", &n, &m, &p, &k); ++k; len = 1 << m;
for (int i=0; i<3; i++)
for (int j=1,x; j<=p; j++){scanf("%d", &x); atk[i] = (atk[i] << 1) + x;}
for (int i=0; i<len; i++)
if (check(i)) ok.emplace_back(i);
int siz = ok.size();
for (int i=0; i<siz; i++)
for (int j=0; j<siz; j++) M[i][j] = check(ok[i], ok[j]);
M = qpow(M, n-1);
u32 ans = 0;
for (int i=0; i<siz; i++)
for (int j=0; j<siz; j++) ans += M[i][j];
printf("%u\n", ans);
return 0;
}
PKUSC2018 最大前缀和
考虑一个前缀可以成为「最大前缀和」当且仅当：
- 这个前缀的每个真后缀和都不小于 \(0\) .
- 这个前缀的补的每个前缀和都小于 \(0\) .
条件分别限制了前缀和它的补，可以想到分别约束后拼起来 .
那么令 \(f_S\) 为 \(S\) 满足条件 \(1\) 的方案数，\(g_S\) 为 \(S\) 的补满足条件 \(2\) 的方案数（这两个状态的定义都认为 \(S\) 是合法最大前缀和），那么有转移：
\[\begin{aligned}&f_{S}=\sum_{\operatorname{sum}(S\mathop{\setminus}\{u\})\ge 0}f_{S\mathop{\setminus}\{u\}}\\&g_{S}=[\operatorname{sum}(S)<0]\sum g_{S\mathop{\setminus}\{u\}}\end{aligned}\tag{$\text{where }u\in S$} \]其中 \(\operatorname{sum}(S)\) 表示集合 \(S\) 内元素之和 .
于是即可做到 \(\Theta(n2^n)\)，可以通过 . 有一些细节需要特殊处理 .
Code
const int N = 22, S = 1048600, P = 998244353;
int n, a[N], f[S], g[S], sum[S];
int main()
{
scanf("%d", &n); int m = 1 << n;
for (int i=1; i<=n; i++) scanf("%d", a+i);
for (int i=0; i<m; i++)
for (int j=1; j<=n; j++)
if (i & (1 << (j-1))) (sum[i] += a[j]) %= P;
g[0] = 1;
for (int i=0; i<n; i++) f[1 << i] = 1;
for (int i=0; i<m; i++)
for (int j=1; j<=n; j++)
{
if (i & (1 << (j-1))) continue;
int k = i | (1 << (j-1));
if (sum[k] - a[j] >= 0) (f[k] += f[i]) %= P;
if (sum[k] < 0) (g[k] += g[i]) %= P;
}
int ans = 0;
for (int i=0; i<m; i++) (ans += 1ll * sum[i] * f[i] % P * g[(m-1) ^ i] % P) %= P;
printf("%d\n", (ans + P) % P);
return 0;
}
NOI2015 寿司晚宴
素因子方向的问题应当考虑根号分治，观察可以发现不小于 \(23\) 的素因子最多出现一次 . 于是只有 \(8\) 个可能出现大于一次的素因子 .
称小于 \(23\) 的素因子为「小素因子」，否则为「大素因子」. 那么考虑如何排除大素因子的影响，考虑将 \(2\dots n\) 按其最大素因子排序，那么包含每个大素因子的数就处在一个连续段内 .
则令 \(dp_{i,S_1,S_2}\) 表示选到第 \(i\) 个数，小 G 和小 W 选的数所包含的小素因子分别为 \(S_1,S_2\) 时的方案数 .
对于每个连续段分别 DP，令 \(g_{i,S_1,S_2}\) 表示到 \(i\) 且 \(i\) 所在连续段只被小 G 选的方案数，\(w_{i,S_1,S_2}\) 表示到 \(i\) 且 \(i\) 所在连续段只被小 W 选的方案数（都限制至少选一个），那么每次进入连续段的时候把 \(dp\) 复制到 \(g,w\) 里，离开连续段的时候再更新 \(dp\) 即可 .
\(g,w\) 的转移就是背包比较简单，对 \(dp\) 的贡献要写 \(dp_{i,S_1,S_2}\gets g_{i,S_1,S_2}+w_{i,S_1,S_2}+dp_{i,S_1,S_2}\)，加上的是连续段内啥都不选的情况 .
这样的时间复杂度是 \(\Theta(n4^{\pi(\sqrt n)})\)，已经可以通过，注意到一个满足 \(S_1\cap S_2\) 的状态一定不合法，那么状态数可以被优化到 \(3^{\pi(\sqrt n)}\)，这样的时间复杂度就是 \(\Theta(n3^{\pi(\sqrt{n}))})\) .
要滚动数组不然空间不太行 . 代码是 \(\Theta(n4^{\pi(\sqrt n)})\) 做法 .
Code
const int N = 555, S = 260, tpr[] = {2, 3, 5, 7, 11, 13, 17, 19}, st = 1 << 8;
int n, p, dp[2][S][S], g[2][S][S], w[2][S][S], lp[N], id[N], factor[N];
int main()
{
scanf("%d%d", &n, &p);
for (int i=1; i<=n; i++)
{
int tmp = i; id[i] = i;
for (int j=0; j<8; j++)
while (!(tmp % tpr[j])){tmp /= tpr[j]; factor[i] |= 1 << j;}
lp[i] = tmp;
}
stable_sort(id+1, id+1+n, [&](int i, int j){return lp[i] < lp[j];});
dp[1][0][0] = 1;
for (int k=2; k<=n; k++)
{
int x = id[k], now = k & 1, lst = now ^ 1;
for (int i=0; i<st; i++)
for (int j=0; j<st; j++){dp[now][i][j] = dp[lst][i][j]; g[now][i][j] = g[lst][i][j]; w[now][i][j] = w[lst][i][j];}
for (int i=0; i<st; i++)
for (int j=0; j<st; j++)
{
if (lp[x] == 1)
{
if (!(factor[x] & i)) (dp[now][i][j | factor[x]] = dp[now][i][j | factor[x]] + dp[lst][i][j]) %= p;
if (!(factor[x] & j)) (dp[now][i | factor[x]][j] = dp[now][i | factor[x]][j] + dp[lst][i][j]) %= p;
}
else if (lp[x] != lp[id[k-1]])
{
(dp[now][i][j] += (g[now][i][j] + w[now][i][j]) % p) %= p;
g[now][i][j] = w[now][i][j] = dp[now][i][j];
}
else
{
if (!(factor[x] & i)) (g[now][i][j | factor[x]] = (g[now][i][j | factor[x]] + g[lst][i][j]) % p + dp[now][i][j]) %= p;
if (!(factor[x] & j)) (w[now][i | factor[x]][j] = (w[now][i | factor[x]][j] + w[lst][i][j]) % p + dp[now][i][j]) %= p;
}
}
}
int ans = 0;
for (int i=0; i<st; i++)
for (int j=0; j<st; j++)
if (!(i & j)) (ans += ((dp[n&1][i][j] + g[n&1][i][j]) % p + w[n&1][i][j]) % p) %= p;
printf("%d\n", ans);
return 0;
}
ZJOI2016 小星星
一道同时出现在「状压dp」和「状压进阶」专题的传奇题目 .
首先可以想到一个朴素 DP 是令 \(dp_{u,x,S}\) 表示 \(u\) 点对应标号 \(x\)，子树内标号集合为 \(S\) 的方案数，那么转移是子集卷积，这样直接枚举子集就 \(\Theta(n^23^n)\) 了，但是过不去 .
考虑放宽限制后容斥，集合方向问题可以考虑子集反演，那么就只需要处理子树内标号集合为 \(S\) 的子集方案数，这样可以沿用朴素 DP 的方法，不过不用记 \(S\) 了，那么就是 \(\Theta(n^2)\) 的 DP 了，算上枚举全集的子集的复杂度就是 \(\Theta(n^22^n)\) 了，这样就可以过了 .
不放代码了 .
JSOI2016 位运算
挺强的题目 .
首先考虑做 \(k=1\) 也就是重复一次的情况，对于互不相同的限制，不难想到的是钦定一个顺序，那么考虑设计一个类似 \(n\) 维数位 DP 的东西，维护 \(2^n\) 长的状态来表示每一位是否「顶格」，具体的，令 \(dp_{i,S}\) 表示考虑到第 \(i\) 位，若选的不降序列在前 \(i\) 位是 \(\{x_n\}\)，那么 \(S\) 记录的是对于每个 \(i\) 是否有 \(x_i=x_{i+1}\) .
转移和数位 DP 的形式是一样的，考虑 \(\{x\}\) 的第 \(i\) 位填什么即可 .
这样如果直接应对 \(k\ge 1\) 的情况就是 \(\Theta(|R|2^{2n}n)\) 的复杂度，不能通过 . 不过在 \(k\) 次重复中对于每轮转移它的转移矩阵是相同的，那么使用矩阵快速幂即可做到 \(\Theta(2^{3n}n(n|S|+\log k))\)，这样就可以过了 .
Code
const int N = 11, L = 55, M = 150, P = 1e9 + 7;
int n, k, dp[L][M], up[N];
string s;
struct matrix
{
const static int n = 130;
int a[M][M];
matrix(char type = 'O'){memset(a, 0, sizeof a); if (type == 'I'){for (int i=0; i<=n; i++) a[i][i] = 1;}}
matrix operator * (const matrix& rhs)
{
matrix res;
for (int i=0; i<=n; i++)
for (int k=0; k<=n; k++)
for (int j=0; j<=n; j++) (res[i][j] += 1ll * a[i][k] * rhs[k][j] % P) %= P;
return res;
}
matrix& operator *= (const matrix& rhs){return *this = *this * rhs;}
const int* operator [](const u32& id) const {return a[id];}
int* operator [](const u32& id){return a[id];}
}A, trans;
matrix qpow(matrix a, ll n)
{
matrix ans('I');
while (n)
{
if (n & 1) ans *= a;
a *= a; n >>= 1;
} return ans;
}
int main()
{
cin >> n >> k >> s; int l = s.length(); s = "$" + s;
int m = 1 << n;
for (int h=0; h<m; h++)
{
memset(dp, 0, sizeof dp);
dp[0][h] = 1;
for (int i=1; i<=l; i++)
for (int j=0; j<m; j++)
{
if (!dp[i-1][j]) continue;
for (int k=0; k<m; k++)
if (__builtin_popcount(k) & 1 ^ 1)
{
up[0] = s[i] - '0';
for (int l=1; l<=n; l++) up[l] = k >> (l-1) & 1;
bool ok = true;
int now = 0;
for (int l=1; l<=n; l++)
if (j >> (l-1) & 1)
{
if (up[l] > up[l-1]){ok = false; break;}
if (up[l] == up[l-1]) now |= 1 << (l-1);
}
if (ok) (dp[i][now] += dp[i-1][j]) %= P;
}
}
for (int i=0; i<m; i++) trans[h][i] = dp[l][i];
}
A[0][m-1] = 1;
printf("%d\n", (A * qpow(trans, k))[0][0]);
return 0;
}
THUWC2017 随机二分图
根据期望线性性，就是问每组完美匹配的生成概率之和 .
先考虑 \(k=0\) 怎么做，就是很平凡的状压 DP，令 \(dp_{S,T}\) 表示左部匹配 \(S\)，右部匹配 \(T\) 的概率和，则
\[dp_{S,T}=\sum_{u\notin S,v\notin T}dp_{S\setminus\{u\},T\setminus\{v\}}P(u,v) \]其中 \(P(u,v)\) 是边 \((u,v)\) 的出现概率 . 额外需要钦定一下加点的顺序不然会算重 .
再看一眼发现状态满足 \(|S|=|T|\) 才合法所以实际上只有 \(\sum_i\binom ni^2=\binom{2n}n\) 个合法状态，记搜跑还是完全可以的 .
考虑把 \(k>0\) 的情况归约到 \(k=0\)：
- 对于 \(k=1\) 的两条边 \((u_1,v_1),(u_2,v_2)\) 来说，对于一组完美匹配，仅出现两边中一个的概率为 \(\frac12\) 这个没有问题，不过同时出现两边时的概率为 \(\frac14\)，于是考虑加一个四元边 \((u_1,v_1,u_2,v_2)\)，表示左部同时匹配上 \(u_1,u_2\)，右部同时匹配上 \(v_1,v_2\)，概率设为 \(\frac14\) 即可 .
- 对于 \(k=2\) 的两条边 \((u_1,v_1),(u_2,v_2)\) 来说，沿用 \(k=1\) 时的做法，加入四元边 \((u_1,v_1,u_2,v_2)\) 概率为 \(-\frac14\) 即可 .
对于四元边的实现方式可以参考代码 .
Code
const int N = 70000, P = 1e9 + 7;
int n, m;
struct Edge{int u, v, w; Edge(int u, int v, int w) : u(u), v(v), w(w){}};
vector<Edge> e;
unordered_map<int, int> memo[N];
int dp(int S, int T)
{
if (!S) return 1;
auto ptr = memo[S].find(T);
if (ptr != memo[S].end()) return ptr -> second;
int ans = 0;
for (Edge e : e)
{
if (((S | e.u) != S) || ((T | e.v) != T) || (S >= e.u * 2)) continue;
(ans += 1ll * dp(S ^ e.u, T ^ e.v) * e.w % P) %= P;
}
return memo[S][T] = (ans + P) % P;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i=1, opt, u1, v1, u2, v2; i<=m; i++)
{
scanf("%d%d%d", &opt, &u1, &v1); u1 = 1 << (u1-1); v1 = 1 << (v1-1);
e.emplace_back(Edge(u1, v1, (P+1) / 2));
if (opt)
{
scanf("%d%d", &u2, &v2); u2 = 1 << (u2-1); v2 = 1 << (v2-1);
e.emplace_back(Edge(u2, v2, (P+1) / 2));
if ((u1 & u2) || (v1 & v2)) continue;
if (opt == 1) e.emplace_back(Edge(u1 | u2, v1 | v2, (P+1) / 4));
else e.emplace_back(Edge(u1 | u2, v1 | v2, -(P+1) / 4));
}
}
printf("%lld\n", 1ll * dp((1 << n) - 1, (1 << n) - 1) * (1 << n) % P);
return 0;
}
PKUWC2018 随机算法
竟然有看起来很平凡做法，来自 lhm .
令 \(dp_S\) 表示得到点集 \(S\) 内点的最大独立集的概率，那么
\[dp_S=\dfrac1{|S|}\sum_{\operatorname{isiz}(S)=\operatorname{isiz}(T)+1}dp_T \]其中 \(\operatorname{isiz}(S)\) 表示点集 \(S\) 的导出子图的最大独立集大小，这个可以状压 DP 预处理 .
即得 \(\Theta(n2^n)\) 算法 .
Code
const int N = 22, S = 1.3e6, P = 998244353;
int n, m, e[N], siz[S], dp[S], inv[N];
inline void init(int n)
{
inv[1] = 1;
for(int i=2; i<=n; i++) inv[i] = 1ll * (P - P/i) * inv[P % i] % P;
}
int main()
{
scanf("%d%d", &n, &m); init(n); int s = 1 << n;
for (int i=1; i<=n; i++){e[i] = 1 << (i-1); siz[i] = 1;}
for (int i=0, u, v; i<m; i++){scanf("%d%d", &u, &v); e[u] |= 1 << (v-1); e[v] |= 1 << (u-1);}
for (int i=1; i<s; i++)
for (int j=1; j<=n; j++)
if (i & (1 << (j-1))) chkmax(siz[i], siz[i ^ (i & e[j])] + 1);
dp[0] = 1;
for (int i=1; i<s; i++)
{
for (int j=1; j<=n; j++)
if ((i & (1 << j-1)) && (siz[i] == siz[i ^ (i & e[j])] + 1)) (dp[i] += dp[i ^ (i & e[j])]) %= P;
dp[i] = 1ll * dp[i] * inv[__builtin_popcount(i)] % P;
}
printf("%d\n", dp[s-1]);
return 0;
}
JLOI2016 字符串覆盖
弃疗了 .
等我会了再补吧（虽然可能会不了了）.
USACO13JAN Island Travels G
翻译有点歧义，「你最少要经过几个浅水区」意味着重复浅水区只算一次，应改为「最少需几次游泳」.
水题啊，首先把连通块缩起来然后处理出两两之间的最短路，这个可以 01BFS 处理 . 然后就是 TSP 了，直接状压 DP 即可解决 .
时间复杂度是 \(\Theta(nm+d2^d)\)，其中 \(d\) 是岛屿数量 .
Code
const int X = 16, N = 55, S = 40000, dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, INF = 0x3f3f3f3f;
int n, m, d[N][N], id[N][N], val[X][X], dp[S][X], cc;
pii frm[N][N];
bool vis[N][N];
string s[N];
inline void bfssb(int sx, int sy)
{
queue<pii> q; q.push(make_pair(sx, sy));
while (!q.empty())
{
pii e = q.front(); int x = e.first, y = e.second; q.pop(); vis[x][y] = true;
frm[x][y] = make_pair(sx, sy);
for (int dir=0; dir<4; dir++)
{
int nx = x + dx[dir], ny = y + dy[dir];
if (!inrange(nx, 1, n) || !inrange(ny, 1, m) || (s[nx][ny] == '.') || (s[nx][ny] == 'S') || vis[nx][ny]) continue;
q.push(make_pair(nx, ny));
}
}
}
inline void bfssp(int x, int y)
{
memset(d, 0x3f, sizeof d);
memset(vis, false, sizeof vis);
deque<pii> q; q.push_back(make_pair(x, y)); d[x][y] = 0;
while (!q.empty())
{
pii e = q.front(); int x = e.first, y = e.second; q.pop_front();
for (int dir=0; dir<4; dir++)
{
int nx = x + dx[dir], ny = y + dy[dir];
if (!inrange(nx, 1, n) || !inrange(ny, 1, m) || (s[nx][ny] == '.') || vis[nx][ny]) continue;
if (s[nx][ny] == 'S'){q.push_back(make_pair(nx, ny)); chkmin(d[nx][ny], d[x][y] + 1);}
else {q.push_front(make_pair(nx, ny)); chkmin(d[nx][ny], d[x][y]);}
vis[nx][ny] = true;
}
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i=1; i<=n; i++){cin >> s[i]; s[i] = "$" + s[i];}
for (int i=1; i<=n; i++)
for (int j=1; j<=m; j++)
if (!vis[i][j] && (s[i][j] == 'X')) bfssb(i, j);
for (int i=1; i<=n; i++)
for (int j=1; j<=m; j++)
if ((s[i][j] == 'X') && !id[frm[i][j].first][frm[i][j].second]) id[frm[i][j].first][frm[i][j].second] = ++cc;
memset(val, 0x3f, sizeof val);
for (int x1=1; x1<=n; x1++)
for (int y1=1; y1<=m; y1++)
{
if ((s[x1][y1] != 'X') || (make_pair(x1, y1) != frm[x1][y1])) continue;
bfssp(x1, y1);
for (int x2=1; x2<=n; x2++)
for (int y2=1; y2<=m; y2++)
if ((s[x2][y2] == 'X') && (make_pair(x2, y2) == frm[x2][y2])) chkmin(val[id[x1][y1]][id[x2][y2]], d[x2][y2]);
}
memset(dp, 0x3f, sizeof dp);
for (int i=1; i<=cc; i++) dp[1 << (i-1)][i] = 0;
int s = 1 << cc;
for (int i=0; i<s; i++)
for (int j=1; j<=cc; j++)
{
if (i & (1 << (j-1))) continue;
for (int k=1; k<=cc; k++)
if (i & (1 << (k-1))) chkmin(dp[i | (1 << (j-1))][j], dp[i][k] + val[k][j]);
}
int ans = INF;
for (int i=1; i<=cc; i++) chkmin(ans, dp[s-1][i]);
printf("%d\n", ans);
return 0;
}
SDOI2009 学校食堂
主要难点在于状态定义，令 \(dp_{i,S,j}\) 表示考虑到 \(i\) 个人，最后一个打饭的人是 \(i+j\)，它自己和后面 \(7\) 位打饭的状态为 \(S\) 的最少时间 .
转移就比较简单了，如果 \(S\) 已经包含 \(i\) 了就直接转移到 \(dp_{i+1,S\setminus\{i\},j-1}\) 即可，否则枚举 \(S\) 中的一个满足前面同学忍耐度的 \(0\) 并转移过去即可 .
时间复杂度单次 \(\Theta(nV^22^V)\) 其中 \(V=\max_i\{B_i\}\) .
实现细节上 \(S\) 记录相对位置好实现一点 . \(k\) 的有效范围是 \([-8,8)\) 需要平移下标 .
Code
const int N = 1234, K = 17, S = 270, INF = 0x3f3f3f3f, mov = 8, s = 256;
int n, t[N], b[N], dp[N][S][K];
int main()
{
#ifndef ONLINE_JUDGE
filein("i");
#endif
int T; scanf("%d", &T);
while (T--)
{
scanf("%d", &n);
for (int i=1; i<=n; i++) scanf("%d%d", t+i, b+i);
memset(dp, 0x3f, sizeof dp); dp[1][0][mov-1] = 0;
for (int i=1; i<=n; i++)
for (int j=0; j<s; j++)
for (int k=-8; k<8; k++)
{
if (dp[i][j][k+mov] > INF / 1.5) continue;
if (j & 1){chkmin(dp[i + 1][j >> 1][k + mov - 1], dp[i][j][k + mov]); continue;}
int bound = INF;
for (int l=0; l<8; l++)
{
if (i + l > bound) break;
if (j & (1 << l)) continue;
chkmin(bound, i + l + b[i + l]);
chkmin(dp[i][j | (1 << l)][l + mov], dp[i][j][k + mov] + (i + k ? (t[i + k] ^ t[i + l]) : 0));
}
}
int ans = INF;
for (int i=0; i<=8; i++) chkmin(ans, dp[n+1][0][i]);
printf("%d\n", ans);
}
return 0;
}