标签 dp 下的文章

题目链接：CF1466H Finding satisfactory solutions

题意：

由于洛谷目前的中文题面过于简洁，导致看完中文题面之后本题就已经解决了一半，所以我来简单翻译一下英文题面。

有 $n$ 个人，第 $i$ 个人初始的时候手上有物品 $i$。
他们之间可以交换物品，每个人恰好拿到一个物品。而每个人有对物品的偏好，第 $i$ 个人的偏好用排列 $\{s_{i,n}\}$ 来表示。第 $i$ 个人相较物品 $y$ 更喜欢物品 $x$，当且仅当在排列 $\{s_{i,n}\}$ 中 $x$ 在 $y$ 之前。
对于一个物品交换的排列 $p$，表示第 $i$ 个物品最后到了 $p_i$ 的手上。对于一个非空的，人的子集 $S$，如果子集内部的人，使用子集内所有人初始手上的物品进行交换，可以达到以下结果：

  1. 不存在一个人 $x\in S$，在子集内交换后得到物品 $y\in S$，且第 $x$ 个人比起 $y$ 更喜欢 $p_x$。
  2. 至少存在一个人 $x\in S$，在子集内交换后得到物品 $y\in S$，且第 $x$ 个人比起 $p_x$ 更喜欢 $y$。

则称这样一个子集 $S$ 是“不稳定”的。一个物品交换的排列 $p$ 是“稳定”的，当且仅当不存在一个“不稳定”的子集。
现给出一个物品交换的排列 $p$，求有多少种 $\{\{s_{1,n}\},\{s_{2,n}\}\cdots,\{s_{n,n}\}\}$ 使得 $p$ 是“稳定”的。
（可以证明，对于一组 $\{\{s_{1,n}\},\{s_{2,n}\}\cdots,\{s_{n,n}\}\}$，恰好存在一个 $p$ 是“稳定”的）
$1\le n\le 40$。






- 阅读剩余部分 -

题目链接：P4229 某位歌姬的故事

题意：

计数长度为 $n$ 的序列 $\{h_n\}$，满足 $\forall h_i\in[1,A]\cap \mathbb{Z}$，且满足 $Q$ 个限制，第 $i$ 个限制形如：$\max_{j=l_i}^{r_i} h_j=m_i$。

$1\le T\le 20, 1\le n,A\le 9\times 10^8,1\le Q\le 500$。

将序列按照 $Q$ 的端点离散化，则以下可以认为 $n,Q$ 同阶。

设 $\text{mx}_i$ 表示第 $i$ 个位置的元素可以达到的最大值，这可以对覆盖当前位置的每个限制暴力取 $\min$ 得到。

对于一个限制 $(l_i,r_i,m_i)$，显然只有区间 $[l_i,r_i]$ 中，$\text{mx}_x=m_i$ 的位置可能使得限制满足。因为若 $\text{mx}_x<m_i$，则说明 $x$ 这个位置被一个更紧的限制被困住了；$\text{mx}_x>m_i$ 说明区间 $i$ 根本没覆盖到 $x$。这说明，$\text{mx}_x$ 取值不同的位置互不影响。

于是枚举 $\text{mx}_x$ 的值 $k$，将 $\text{mx}_x=k$ 的下标拿出来做 $\text{dp}$。

则问题转变为：

计数长度为 $n$ 的序列 $\{a_n\}$，满足 $\forall a_i\le k$，且满足若干限制，第 $i$ 个限制形如：$[l_i,r_i]$ 中存在一个元素顶到 $k$ 的上界。

显然有：设 $\text{dp}_{i,j}$ 表示填了前 $i$ 个位置，最后一个顶到 $k$ 的位置是 $j$ 的方案数。转移显然。

需要注意的是，需要特殊判断没有被覆盖到的位置，他们可以在 $[1,A]$ 中任选。

时间复杂度 $\mathcal{O}(TQ^2)$。

//Code By CXY07
#include<bits/stdc++.h>
using namespace std;

//#define FILE
#define int long long
#define file(FILENAME) freopen(FILENAME".in", "r", stdin), freopen(FILENAME".out", "w", stdout)
#define randint(l, r) (rand() % ((r) - (l) + 1) + (l))
#define LINE() cout << "LINE = " << __LINE__ << endl
#define debug(x) cout << #x << " = " << x << endl
#define abs(x) ((x) < 0 ? (-(x)) : (x))
#define inv(x) qpow((x), mod - 2)
#define lowbit(x) ((x) & (-(x)))
#define ull unsigned long long
#define pii pair<int, int>
#define LL long long
#define mp make_pair
#define pb push_back
#define scd second
#define vec vector
#define fst first
#define endl '\n'

const int MAXN = 1010;
const int INF = 2e9;
const double eps = 1e-6;
const double PI = acos(-1);
//const int mod = 1e9 + 7;
const int mod = 998244353;
//const int G = 3;
//const int base = 131;

int T, n, Q, A, Ans = 1, N;
int L[MAXN], R[MAXN], m[MAXN], p[MAXN];
int dp[MAXN][MAXN], mx[MAXN], lim[MAXN];
int idx[MAXN], idxc;
vec<int> v;
vec<pii> opt;

template<typename T> inline bool read(T &a) {
    a = 0; char c = getchar(); int f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') {a = a * 10 + (c ^ 48); c = getchar();}
    return a *= f, true;
}

template<typename A, typename ...B>
inline bool read(A &x, B &...y) {return read(x) && read(y...);}

int qpow(int x, int b) {
    int res = 1;
    for(; b; b >>= 1, (x *= x) %= mod) if(b & 1) (res *= x) %= mod;
    return res;
}

int Getid(int x) {
    return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}

int siz(int x) { assert(x < v.size()); return v[x] - v[x - 1]; }

int exist(int m, int s) {
    return (qpow(m, s) - qpow(m - 1, s) + mod) % mod;
}

bool cmp(int x, int y) { return m[x] < m[y]; }

void modadd(int &x, int y) {
    x += y;
    if(x >= mod) x -= mod;
}

void clear() {
    memset(mx, 0x3f, sizeof mx);
    v.clear(); opt.clear(); Ans = 1;
}

int calc(int m, int l, int r) {
    int res = 0; idxc = 0, dp[0][0] = 1;
    for(int i = 1; i <= N; ++i) if(mx[i] == m) idx[++idxc] = i;
    for(int i = l, L1, R1; i <= r; ++i) {
        L1 = *lower_bound(idx + 1, idx + idxc + 1, L[p[i]]);
        R1 = *(lower_bound(idx + 1, idx + idxc + 1, R[p[i]]) - 1);
        lim[R1] = max(lim[R1], L1);
    }
    for(int i = 1; i <= N; ++i) lim[i] = max(lim[i], lim[i - 1]);
    for(int i = 1; i <= idxc; ++i) {
        for(int j = 0; j < idx[i]; ++j) {
            (dp[i][idx[i]] += dp[i - 1][j] * exist(m, siz(idx[i]))) %= mod;
            if(lim[idx[i]] <= j) (dp[i][j] = dp[i - 1][j] * qpow(m - 1, siz(idx[i]))) %= mod;
        }
    }
    for(int i = 1; i <= idx[idxc]; ++i) modadd(res, dp[idxc][i]);
    for(int i = 0; i <= N; ++i) lim[i] = 0;
    for(int i = 1; i <= idxc; ++i)
        for(int j = 0; j <= idx[i]; ++j) dp[i][j] = 0;
    return res;
}

void solve() {
    clear(); read(n), read(Q), read(A); 
    for(int i = 1; i <= Q; ++i) {
        read(L[i]), read(R[i]), read(m[i]); R[i]++;
        opt.pb(mp(L[i], 1)), opt.pb(mp(R[i], -1));
        v.pb(L[i]), v.pb(R[i]), p[i] = i;
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end()); N = v.size();
    for(int i = 1; i <= Q; ++i) {
        L[i] = Getid(L[i]), R[i] = Getid(R[i]);
        for(int j = L[i]; j < R[i]; ++j) mx[j] = min(mx[j], m[i]);
    }
    sort(p + 1, p + Q + 1, cmp);
    for(int l = 1, r; l <= Q; l = r + 1) {
        r = l;
        while(r < Q && m[p[r + 1]] == m[p[l]]) r++;
        Ans = Ans * calc(m[p[l]], l, r) % mod;
    }
    sort(opt.begin(), opt.end()); int cur = 0, pre = 1;
    for(int l = 0, r; l < opt.size(); l = r + 1) {
        if(!cur) Ans = Ans * qpow(A, opt[l].fst - pre) % mod;
        r = l; cur += opt[l].scd;
        while(r + 1 < opt.size() && opt[r + 1].fst == opt[l].fst) cur += opt[++r].scd;
        pre = opt[l].fst;
    }
    Ans = Ans * qpow(A, n - pre + 1) % mod;
    printf("%lld\n", Ans);
}

signed main () {
#ifdef FILE
    freopen("P4229.in", "r", stdin);
    freopen("P4229.out", "w", stdout);
#endif
    read(T);
    while(T--) solve();
    return 0;
}
  1. 1
  2. 2
  3. 3