【題目來源】https://acm.hdu.edu.cn/showproblem.php?pid7239【題目描述】zyb 在訪問莫斯科期間購買了 n 個 matryoshka 玩偶大小分別為 a1、a2、…、an從最小到最大排序。大小為 i 的 matryoshka 可以放入另一個大小為 j 的 matryoshka當且僅當 j?i≥r、 其中r是某個給定的整數(shù)參數(shù)。zyb 希望將所有 n 個 matryoshka 玩偶分成 k 組這樣每個組中都可以形成一個嵌套的 Matryoshka 玩偶其中一組 Matryoska 玩偶的索引為 c1、c2、…、cm1≤c1c2…cm≤n 可以形成嵌套的 matryoshka 玩偶如果 ?1≤ima[ci]r≤a[ci1]。zyb 想知道有多少種方法可以將 n 個玩偶分成 k 組以滿足上述要求。請注意諸如 {{1,2}, {3,4}} 和 {{3,4}, {1,2}} 等劃分被視為相同的方式。由于答案可能太大您只需要輸出答案模 998244353?！据斎敫袷健康谝恍邪麛?shù)T1≤T≤20 表示測試用例的數(shù)量。對于每個測試用例第一行包含三個整數(shù) nkr1≤k≤n≤5000,1≤r≤1e9表示 matryoshka 玩偶的數(shù)量zyb 想要劃分的組的數(shù)量以及參數(shù)。下一行包含 n 個整數(shù) a1、a2、…、an1≤a1≤a2≤...≤an≤1e9表示 matryoshka 玩偶的尺寸?？梢员ＷC ∑n≤所有測試用例中有 50000 個?！据敵龈袷健繉τ诿總€測試用例在一行中輸出一個整數(shù)表示取模 998244353 的答案。???????【輸入樣例】24 3 21 2 3 44 2 11 1 2 2【輸出樣例】32【數(shù)據(jù)范圍】1≤T≤201≤k≤n≤5000,1≤r≤1e91≤a1≤a2≤...≤an≤1e9【算法分析】有 n 個套娃大小為 a1 ≤a2 ≤... ≤an現(xiàn)在要將這些套娃分成 k 組每組套娃按照大小排序后相鄰兩個套娃之間的大小差距要求r求方案數(shù)。設(shè)f[i][j] 表示將前 i 個套娃分成 j 組的方案數(shù)狀態(tài)轉(zhuǎn)移方程為f[i][j]f[i-1][j-1](新增一組) f[i-1][j]*max(0, j-num(z)) (第 x 的套娃跟之前的放在一組)其中 num(z) 表示 1zi 且ai-razai 的 z 的個數(shù)。時間復雜度為O(n^2)。【算法代碼】HDUhttps://acm.hdu.edu.cn/ 不支持萬能頭文件。#include iostream #include algorithm using namespace std; typedef long long LL; const int M5005; const LL mod998244353; int n,k,r,a[M]; LL f[M][M]; int main() { int T; scanf(%d,T); while(T--) { scanf(%d%d%d,n,k,r); for(int i1; in; i) scanf(%d,a[i]); for(int i0; in; i) { for(int j0; jk; j) f[i][j]0; } f[0][0]1; for(int i1,z1; in; i) { while(zi a[i]-ra[z]) z; int numi-z; for(int jnum1; jmin(i,k); j) { f[i][j](f[i-1][j-1]f[i-1][j]*(j-num))%mod; } } printf(%lld\n,f[n][k]); } return 0; } /* in: 2 4 3 2 1 2 3 4 4 2 1 1 1 2 2 out: 3 2 */【參考文獻】https://acm.hdu.edu.cn/showproblem.php?pid7239https://mp.weixin.qq.com/s/HNISXyopgpO1PmATouxuyg