我们不难发现，假设抽了x张攻击牌，y张强化牌，那么肯定是打出尽可能多张的强化牌后，再开始出攻击牌（当然最少要一张攻击牌）
我们设G(i,j)表示：所有（抽到的攻击牌牌数为i，打出的攻击牌牌数为j）的方案，所产生的攻击值的总和
形式化地说：
考虑到G(i,j)难以一次求出，我们考虑设置一些中间变量
设g[i][j]表示：我们对攻击牌从小大大进行排序，目前选了i张牌，其中最小的牌是第j张的总贡献，其中b[j]表示第j小的牌的攻击值
当i=1时，有$g[i][j]=b[j]$
当i>1时，有$g[i][j]=b[j]\times \binom{n-j+1}{i}+\sum\limits_{k=j+1}^{n} g[i-1][k]$
后面那个$\sum$我们可以通过求前缀和，实现快速求解
考虑如何通过g(i,j)求解G(i,j)
不难推出：$G(i,j)=\sum\limits_{k=1}^{n-j+1} g[i][k]$
我们设F(i,j)表示：所有（抽到的强化牌牌数为i，打出的强化牌数为j）的方案里，每一个方案所产生的贡献（抽到的i张牌中，最大的j张牌之积）的和
形式化地说：$F(i,j)=\sum\limits_{S∈强化牌\and|S|=i}S中前j大的牌的强化值之积$
考虑到F(i,j)难以一次求出，我们考虑设置一些中间变量
设f[i][j]表示：我们对强化牌从小大大进行排序，目前选了i张牌，其中最小的牌是第j张的总贡献，其中a[j]表示第j小的牌的攻击值
当i=1时，有$f[i][j]=a[j]$
当i>1时，有$f[i][j]=a[j]\times \sum\limits_{k=j+1}^{n} f[i-1][k]$
后面那个$\sum$我们可以通过求前缀和，实现快速求解
考虑如何通过f(i,j)求解F(i,j)
不难推出：$F(i,j)=\sum\limits_{k=1}^{n-j+1} f[i][k]$
最后我们要求的答案ans，假设当前，我们抽到的强化牌数量为i
若i<k，则$ans+=F(i,i)\times G(m-i,k-i)$
若i≥k，则$ans+=F(i,k-1)\times G(m-i,1)$
完结撒花~
1 #include <algorithm> 2 #include <iostream> 3 #include <cstring> 4 #include <cstdio> 5 using namespace std; 6 typedef long long ll; 7 const int mod=998244353; 8 int T, n, m, k, a[1505], b[1505], c[3005][3005], f[1505][1505]; 9 int g[1505][1505], sum[1505]; 10 int F(int x, int y){ 11 if(x<y) return 0; 12 if(!y) return c[n][x]; 13 int re=0; 14 for(int j=x-y+1; j<=n-y+1; j++) 15 re = (re + (ll)f[y][j]*c[j-1][x-y]%mod) % mod; 16 //感性理解一下……大概就是把x-y张不打出的牌放到j前头，这里我讲不太清QAQ 17 return re; 18 } 19 int G(int x, int y){ 20 if(x<y) return 0; 21 int re=0; 22 for(int j=x-y+1; j<=n-y+1; j++) 23 re = (re + (ll)g[y][j]*c[j-1][x-y]%mod) % mod; 24 return re; 25 } 26 int main(){ 27 cin>>T; 28 for(int i=0; i<=3000; i++){ 29 c[i][0] = 1; 30 for(int j=1; j<=i; j++) 31 c[i][j] = (c[i-1][j-1] + c[i-1][j]) % mod; 32 } 33 while(T--){ 34 memset(f, 0, sizeof(f)); 35 memset(g, 0, sizeof(g)); 36 scanf("%d %d %d", &n, &m, &k); 37 for(int i=1; i<=n; i++) scanf("%d", &a[i]); 38 for(int i=1; i<=n; i++) scanf("%d", &b[i]); 39 sort(a+1, a+1+n);//跟牌的顺序无关，可以sort 40 sort(b+1, b+1+n); 41 for(int i=1; i<=n; i++){ 42 f[1][i] = a[i];//初始化f[][]，显然只选1张的倍率之和是a[i] 43 sum[i] = (sum[i-1] + a[i]) % mod;//前缀和，方便转移 44 } 45 for(int i=2; i<=n; i++){ 46 for(int j=1; j<=n-i+1; j++) 47 f[i][j] = (ll)a[j] * (sum[n]-sum[j]+mod) % mod; 48 //打了i张牌，最前头的是第j张，那它就是f[i-1][j+1..n]的和再乘上第j号元素。这个转移的思想是枚举在打了i-1张牌的时候最前头的是哪一张 49 for(int j=1; j<=n; j++) 50 sum[j] = (sum[j-1] + f[i][j]) % mod; 51 } 52 for(int i=1; i<=n; i++){ 53 g[1][i] = b[i]; 54 sum[i] = (sum[i-1] + b[i]) % mod; 55 } 56 for(int i=2; i<=n; i++){ 57 for(int j=1; j<=n-i+1; j++) 58 g[i][j] = ((ll)b[j]*c[n-j][i-1]%mod+(sum[n]-sum[j]+mod)%mod) % mod; 59 //打了i张牌，最前头的是第j张。注意g代表的是（不加强化的）攻击力和。在这种情况下，打了i-1张牌的总情况是c[n-j][i-1]种（j+1..n中选i-1个的方案数），这是第一项；第二项就是继承自g[i-1][j+1..n] 60 for(int j=1; j<=n; j++) 61 sum[j] = (sum[j-1] + g[i][j]) % mod; 62 } 63 int ans=0; 64 for(int i=0; i<m; i++) 65 if(i<k) ans = (ans + (ll)F(i,i)*G(m-i,k-i)%mod) % mod; 66 else ans = (ans + (ll)F(i,k-1)*G(m-i,1)%mod) % mod; 67 printf("%d\n", ans); 68 } 69 return 0; 70 }