2024CCPC网络预选赛 I. 找行李 【DP】

传送门：https://codeforces.com/gym/105336

思路

（思路参考于官方题解，对一些地方进行详细说明）
令 $g(d)$ 表示答案大于等于 $d$ 的方案数，那么很显然答案就是：${\sum }_{d=1}^{\infty }g(d)$
这是因为：对于一个答案 $d$，它会在 $[1,d]$ 各算一次

考虑枚举 $d$，那么对于每个人 $i$，只能选择 $a_i-d$ 及之前的行李配对给他
如果我们对每个人的位置排序，我们可以发现每个人左边的行李是确定的，且 $i$ 可选的行李一定是 $i+1$ 的可选行李的子集，那么这里我们就可以转化成一个很经典的 $dp$

定义 $d{p}_{i,j}$ 为：前 $i$ 个人，选了 $j$ 个物品的方案数，假设第 $i$ 个人可选的行李数量为 $k$ 个，他只能选择一个或者不选
那么我们有转移：

$$d{p}_{i,j}=d{p}_{i-1,j}+d{p}_{i-1,j-1}\times (k-(j-1))$$

后面意思就是，$k$ 个物品已经选了 $j-1$ 个，还有 $k-j+1$ 个可选，从中选一个即可。
这里我们可以看成将没选的按照编号排个序，就可以不重不漏地选择了，共有 $k-j+1$ 个物品可选

上述 $k$ 我们可以使用前缀和快速得到

边界设置 $d{p}_{0,0}=1$ 即可

时间复杂度：$O(n^3)$

#include<bits/stdc++.h>
#define fore(i,l,r)	for(int i=(int)(l);i<(int)(r);++i)
#define fi first
#define se second
#define endl '\n'
#define ull unsigned long long
#define ALL(v) v.begin(), v.end()
#define Debug(x, ed) std::cerr << #x << " = " << x << ed;const int INF=0x3f3f3f3f;
const long long INFLL=1e18;typedef long long ll;template<class T>
constexpr T power(T a, ll b){T res = 1;while(b){if(b&1) res = res * a;a = a * a;b >>= 1;}return res;
}constexpr ll mul(ll a,ll b,ll mod){ //快速乘，避免两个long long相乘取模溢出ll res = a * b - ll(1.L * a * b / mod) * mod;res %= mod;if(res < 0) res += mod; //误差return res;
}template<ll P>
struct MLL{ll x;constexpr MLL() = default;constexpr MLL(ll x) : x(norm(x % getMod())) {}static ll Mod;constexpr static ll getMod(){if(P > 0) return P;return Mod;}constexpr static void setMod(int _Mod){Mod = _Mod;}constexpr ll norm(ll x) const{if(x < 0){x += getMod();}if(x >= getMod()){x -= getMod();}return x;}constexpr ll val() const{return x;}explicit constexpr operator ll() const{ return x; //将结构体显示转换为ll类型： ll res = static_cast<ll>(OBJ)}constexpr MLL operator -() const{ //负号，等价于加上ModMLL res;res.x = norm(getMod() - x);return res;}constexpr MLL inv() const{assert(x != 0);return power(*this, getMod() - 2); //用费马小定理求逆}constexpr MLL& operator *= (MLL rhs) & { //& 表示“this”指针不能指向一个临时对象或const对象x = mul(x, rhs.x, getMod()); //该函数只能被一个左值调用return *this;}constexpr MLL& operator += (MLL rhs) & {x = norm(x + rhs.x);return *this;}constexpr MLL& operator -= (MLL rhs) & {x = norm(x - rhs.x);return *this;}constexpr MLL& operator /= (MLL rhs) & {return *this *= rhs.inv();}friend constexpr MLL operator * (MLL lhs, MLL rhs){MLL res = lhs;res *= rhs;return res;}friend constexpr MLL operator + (MLL lhs, MLL rhs){MLL res = lhs;res += rhs;return res;}friend constexpr MLL operator - (MLL lhs, MLL rhs){MLL res = lhs;res -= rhs;return res;}friend constexpr MLL operator / (MLL lhs, MLL rhs){MLL res = lhs;res /= rhs;return res;}friend constexpr std::istream& operator >> (std::istream& is, MLL& a){ll v;is >> v;a = MLL(v);return is;}friend constexpr std::ostream& operator << (std::ostream& os, MLL& a){return os << a.val();}friend constexpr bool operator == (MLL lhs, MLL rhs){return lhs.val() == rhs.val();}friend constexpr bool operator != (MLL lhs, MLL rhs){return lhs.val() != rhs.val();}
};const ll mod = 998244353;
using Z = MLL<mod>;
template<>
ll MLL<0ll>::Mod = 998244353;
//using Z = MLL<0ll>;const int N = 505;int main(){std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);int n, m;std::cin >> n >> m;std::vector<int> a(n), b(m);std::vector<int> cnt(N, 0);fore(i, 0, n){std::cin >> a[i];++cnt[a[i]];}fore(i, 0, m) std::cin >> b[i];std::sort(ALL(b));fore(i, 1, N) cnt[i] += cnt[i - 1];Z ans = 0;fore(d, 1, N - 4){std::vector<Z> dp(m + 1);dp[0] = 1;for(auto p : b){auto f = dp;int num = (p - d >= 0 ? cnt[p - d] : 0);fore(j, 1, std::min(num, m) + 1) dp[j] += f[j - 1] * (num - j + 1);}fore(k, 1, m + 1) ans += dp[k];}std::cout << ans << endl;return 0;
}