套路滿滿的樣子(o°ω°o) 實(shí)際上在發(fā)現(xiàn)‘比...多 \(K\) 實(shí)際上就是要求糖果能量大于藥片能量的組數(shù)為 \(K'\) 時(shí)，這題的指向性就很明確了。按照慣例來說，我們應(yīng)當(dāng)試圖用‘至少’來求出‘恰好’的方案數(shù)。

　　先考慮容斥的部分：如果可以求出每一個(gè)糖果集合 \(T\) 使得 \(T\) 中的所有糖果在最后的組合方案中能量都能夠大于所匹配的藥片的能量的方案數(shù) \(h_{i}\)，那么令

\(ans = \sum_{T\subseteq S}^{\ }f_{t}*h_{t}\)

由于只要恰好為 \(K\) 的方案數(shù)

所以一個(gè)‘糖果大于藥片’組數(shù)為 \(T\) 的方案應(yīng)對答案產(chǎn)生貢獻(xiàn)為：

\(g_{x}=\sum_{i = 0}^{x}f_{i}*\binom{x}{i}=[x = K]\)

二項(xiàng)式反演，即可得：

\(f_{x}=\sum_{i = 0}^{x}(-1)^{x - K}*\binom{x}{K}\)

　　解決了容斥系數(shù)，再考慮如何求出至少 \(i\) 組中糖果能量大于藥片能量的方案數(shù)？由于題目允許 \(n^{2}\) 的復(fù)雜度，不妨大膽設(shè)dp狀態(tài) \(dp[i][j]\) 表示將糖果與藥片均從小到大排序后，糖果組合到第 \(i\) 個(gè)，已經(jīng)有 \(j\) 組糖果 > 藥片的方案數(shù)。考慮當(dāng)前糖果是組合一個(gè)比自己大的還是暫不考慮即可。最后求得的方案數(shù)中，雖然保證了有 \(x\) 組糖果 > 藥片，但并沒有對剩下的元素提出要求。所以都乘上一個(gè) \(fac[n - x]\) 即為所求。

　　完美解決ヾ(o′?｀o)ﾉ

#include <bits/stdc++.h> using namespace std; #define maxn 3005 #define CNST 3000 #define mod 1000000009 int n, K, ans, C[maxn][maxn], f[maxn][maxn]; int fac[maxn], g[maxn], rec[maxn], a[maxn], b[maxn];int read() {int x = 0, k = 1;char c; c = getchar();while(c < '0' || c > '9') { if(c == '-') k = -1; c = getchar(); }while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();return x * k; }void Up(int &x, int y) { x = (x + y) % mod; } void Pre() {fac[0] = 1; for(int i = 1; i < maxn; i ++) fac[i] = 1ll * fac[i - 1] * i % mod;for(int i = 0; i < CNST; i ++) C[i][0] = 1;for(int i = 1; i < CNST; i ++)for(int j = 1; j < CNST; j ++)C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod; }void DP() {f[0][0] = 1;for(int i = 0; i <= n; i ++)for(int j = 0; j <= i; j ++){int t = i + 1;Up(f[t][j], f[i][j]);if(rec[t] > j) Up(f[t][j + 1], 1ll * f[i][j] * (rec[t] - j) % mod);}for(int i = 1; i <= n; i ++) f[n][i] = 1ll * f[n][i] * fac[n - i] % mod; }void In_ex() {for(int i = K; i <= n; i ++)g[i] = 1ll * (((i - K) & 1) ? -1 : 1) * C[i][K] % mod;for(int i = K; i <= n; i ++) Up(ans, 1ll * g[i] * f[n][i] % mod); }int main() {n = read(), K = read(); Pre(); if(n + K & 1) { printf("0\n"); }else K = (n + K) >> 1;for(int i = 1; i <= n; i ++) a[i] = read();for(int i = 1; i <= n; i ++) b[i] = read();sort(a + 1, a + 1 + n);sort(b + 1, b + 1 + n);for(int i = 1; i <= n; i ++)for(int j = 1; j <= n; j ++)if(b[j] > a[i]) { rec[i] = j - 1; break; }else if(j == n) rec[i] = n;DP(); In_ex();printf("%d\n", (ans + mod) % mod);return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/twilight-sx/p/10162743.html

總結(jié)

以上是生活随笔為你收集整理的【题解】已经没有什么好害怕的了的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。