題目鏈接

(Luogu) https://www.luogu.org/problem/P4859
(bzoj) https://www.lydsy.com/JudgeOnline/problem.php?id=3622

題解

我依然啥都不會啊……

先給\(A,B\)數組從小到大排序。
考慮容斥，設\(f[j]\)表示欽定了\(j\)個滿足\(A>B\), 所有欽定方案的方案數總和。
這個怎么算？dp算。設\(dp[i][j]\)表示前\(i\)個的\(f[j]\), 然后發現轉移的時候并不知道之前選的那些沒有欽定的有幾個比當前的大。
怎么辦？轉換思路，我們考慮先選出欽定的\(B\), 不考慮剩下未欽定的。那么很容易列出方程: \(dp[i][j]=dp[i-1][j]+dp[i-1][j-1]\times (t-i+1)\), 其中\(t\)為\(a_i\)大于\(B\)序列中的多少個數。
最后\(f[j]=dp[n][j]\times (n-j)!\), 完美解決。

容斥怎么辦？思考組合意義或者二項式反演，總之最后是一個式子\(g[i]=\sum^n_{j=i}(-1)^{j-i}{i\choose j}f[j]\), 其中\(g[i]\)表示恰好有\(i\)對\(A>B\)的方案數。

時間復雜度\(O(n^2)\).

代碼

#include<cstdio> #include<cstdlib> #include<cstring> #include<cassert> #include<iostream> #include<algorithm> #define llong long long using namespace std;inline int read() {int x=0; bool f=1; char c=getchar();for(;!isdigit(c);c=getchar()) if(c=='-') f=0;for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^'0');if(f) return x;return -x; }const int N = 2000; const int P = 1e9+9; int a[N+3],b[N+3]; llong dp[N+3][N+3]; llong f[N+3]; llong fact[N+3],finv[N+3]; int n,m;llong quickpow(llong x,llong y) {llong cur = x,ret = 1ll;for(int i=0; y; i++){if(y&(1ll<<i)) {y-=(1ll<<i); ret = ret*cur%P;}cur = cur*cur%P;}return ret; } llong mulinv(llong x) {return quickpow(x,P-2);} llong comb(llong x,llong y) {return x<0||y<0||x<y ? 0ll : fact[x]*finv[y]%P*finv[x-y]%P;}int main() {fact[0] = 1ll; for(int i=1; i<=N; i++) fact[i] = fact[i-1]*i%P;finv[N] = quickpow(fact[N],P-2); for(int i=N-1; i>=0; i--) finv[i] = finv[i+1]*(i+1)%P;scanf("%d%d",&n,&m);if((n+m)&1) {printf("0"); return 0;}m = (n+m)>>1;for(int i=1; i<=n; i++) scanf("%d",&a[i]);for(int i=1; i<=n; i++) scanf("%d",&b[i]);sort(a+1,a+n+1); sort(b+1,b+n+1);dp[0][0] = 1ll;for(int i=1; i<=n; i++){int t = lower_bound(b+1,b+n+1,a[i])-b-1;for(int j=0; j<=i; j++){dp[i][j] = dp[i-1][j];if(j>0 && t-j+1>0) {dp[i][j] = (dp[i][j]+dp[i-1][j-1]*(t-j+1))%P;}}}for(int i=0; i<=n; i++) f[i] = dp[n][i]*fact[n-i]%P;llong ans = 0ll;for(int i=m; i<=n; i++){llong tmp = f[i]*comb(i,m);if((i-m)&1) {ans = (ans-tmp+P)%P;}else {ans = (ans+tmp)%P;}}printf("%lld\n",ans);return 0; }

總結

以上是生活随笔為你收集整理的BZOJ 3622 Luogu P4859 已经没有什么好害怕的了 (容斥原理、DP)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。