难难
BZOJ 4316 isn
给出一个序列
求删除方案数。
对于所有
dp,树状数组,容斥。
假设我们已经算出来了
那么答案可以考虑为
然而明显,有可能在删除到
考虑容斥。
我们只用考虑在长度为
根据定义,长度为
那么对于每一个
然后我们考虑如何计算
令
那么有:
其中
我们发现这就是一个二位数点的问题,通过 BIT 优化即可。
时间复杂度
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2000 + 10, P = 1e9 + 7;
int n, arr[MAXN], f[MAXN][MAXN], cpy[MAXN], rk[MAXN], val[MAXN], g[MAXN], prod[MAXN];
struct BIT {
int bit[MAXN];
void add(int x, int val) { val %= P; for (; x <= n + 1; x += x & (-x)) (bit[x] += val) %= P; }
int sum(int x) { int ret = 0; for(; x; x -= x & (-x)) (ret += bit[x]) %= P; return ret; }
} bit[MAXN];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &arr[i]), cpy[i] = arr[i];
}
sort(arr + 1, arr + n + 1);
int m = unique(arr + 1, arr + n + 1) - arr - 1;
for (int i = 1; i <= n; ++i) rk[i] = lower_bound(arr + 1, arr + m + 1, cpy[i]) - arr + 1, val[rk[i]] = cpy[i];
f[0][0] = 1, bit[0].add(1, 1);
for (int i = 1; i <= n; ++i) {
for (int j = i; j >= 1; --j) {
(f[j][i] += bit[j - 1].sum(rk[i])) %= P, bit[j].add(rk[i], f[j][i]);
}
}
for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) (g[i] += f[i][j]) %= P;
int ans = 0;
prod[1] = 1;
for (int i = 2; i <= n; ++i) prod[i] = (1ll * prod[i - 1] * i) % P;
for (int i = n; i >= 1; --i) {
ll tmp1 = 1ll * g[i] * prod[n - i] % P;
ll tmp2 = 1ll * g[i + 1] * prod[n - i - 1] % P * (i + 1) % P;
(ans += ((tmp1 - tmp2) % P + P) % P) %= P;
}
printf("%d\n", ans);
return 0;
}
做的时候发现自己还是没有理解二位维点 dp 的细节,比如循环顺序之类的。
BZOJ 1566 管道取珠
给出两个串 S, T,均由 'A', 'B' 组成,每次操作可以取出某个串最右边的字符并添加到输出字符串 U 的最左边。令
两种不同的方式定义为存在某次操作,使得第一种取的 S,第二种取的 T;或第一种取的 T,第二种取的 S。
dp
加法具有交换律,故可以不考虑字典序。
一个重要的观察是,
则有一个奇妙重重的 dp 状态与转移(可能是个套路):
令
不难发现,一种状态是所有符合定义的
那么有转移:
滚动数组即可。
时间复杂度
#include <bits/stdc++.h>
using namespace std;
const int P = 1024523;
const int MAXN = 500 + 10;
int n, m, s[MAXN], t[MAXN], f[MAXN][MAXN], g[MAXN][MAXN];
char str[MAXN];
void add(int& a, int b) { a = a + b > P ? a + b - P : a + b; }
int main() {
scanf("%d %d", &n, &m);
scanf("%s", str + 1);
for (int i = 1; i <= n; ++i) s[i] = str[i] == 'A';
s[0] = -1, t[0] = -2;
scanf("%s", str + 1);
for (int i = 1 ;i <= m; ++i) t[i] = str[i] == 'A';
f[0][0] = 1;
for (int i = 1; i <= n + m; ++i) {
for (int j = 0; j <= n; ++j) for (int k = 0; k <= n; ++k) g[j][k] = f[j][k], f[j][k] = 0;
for (int j = max(0, i - m); j <= min(n, i); ++j) {
for (int k = max(0, i - m); k <= min(n, i); ++k) {
if (j && k && s[j] == s[k]) add(f[j][k], g[k - 1][j - 1]);
if (j && s[j] == t[i - k]) add(f[j][k], g[j - 1][k]);
if (k && t[i - j] == s[k]) add(f[j][k], g[j][k - 1]);
if (t[i - j] == t[i - k]) add(f[j][k], g[k][j]);
}
}
if (i == n + m) { printf("%d\n", f[n][n]); return 0; }
}
return 0;
}
玄妙状态与转移。