传送门 https://www.luogu.org/problemnew/show/P4859
思路
大佬都说这是套路题...... 嘤嘤嘤我又被吊打了 \(Q\omega Q\)
显然, 这题是要 \(DP\) 的.
首先思考一下性质:
为了方便, 下面令 \(k=\frac{n+k}{2}\), 即有恰好 \(k\) 组糖果比药片大.
显然,\(a,b\) 数组都要先从小到大排序.(\(a\) 是糖果,\(b\) 是药片)
考虑 \(a_i\) 造成的影响:
1, 若它匹配了一个比它小的 \(b\), 则对于 \(a_j,j>i\), 它匹配比它小的 \(b\) 的方案数少了 \(1\).
2, 若它匹配了一个比它大的 \(b\)...... 似乎又要分类讨论, 状态很难记录.
所以, 我们 \(DP\) 时先考虑第一种的 \(a_i\), 第二种的最后统一分配.
设 \(dp_{i,j}\) 表示前 \(i\) 个 \(a\), 有 \(j\) 个第一种, 方案数.
容易得到
\[ dp_{i,j}=dp_{i-1,j}+(r_i-(j-1))dp_{i-1,j-1} \]
其中 \(r_i\) 表示 \(b\) 中比 \(a_i\) 小的个数.
接下来, 记 \(f_i=(n-i)!dp_{n,i}\), 也就是把 \(n-i\) 个没有匹配的任意分配, 得到至少 \(i\) 个的答案 \(f_i\).
那么恰好 \(i\) 个的答案呢?
从大往小递推, 有
\[ ans_i=f_i-\sum_{j=i+1}^n {j \choose i} ans_j \]
或者用另一种容斥, 有
\[ ans=\sum_{i=k}^n (-1)^{i-k}{i \choose k} f_i \]
复杂度 \(O(n^2)\).
代码
- #include<bits/stdc++.h>
- namespace my_std{
- using namespace std;
- #define pii pair<int,int>
- #define fir first
- #define sec second
- #define MP make_pair
- #define rep(i,x,y) for (int i=(x);i<=(y);i++)
- #define drep(i,x,y) for (int i=(x);i>=(y);i--)
- #define go(x) for (int i=head[x];i;i=edge[i].nxt)
- #define sz 2020
- typedef long long ll;
- const ll mod=1e9+9;
- template<typename T>
- inline void read(T& t)
- {
- t=0;char f=0,ch=getchar();
- double d=0.1;
- while(ch>'9'||ch<'0') f|=(ch=='-'),ch=getchar();
- while(ch<='9'&&ch>='0') t=t*10+ch-48,ch=getchar();
- if(ch=='.')
- {
- ch=getchar();
- while(ch<='9'&&ch>='0') t+=d*(ch^48),d*=0.1,ch=getchar();
- }
- t=(f?-t:t);
- }
- template<typename T,typename... Args>
- inline void read(T& t,Args&... args){read(t); read(args...);}
- void file()
- {
- #ifndef ONLINE_JUDGE
- freopen("a.txt","r",stdin);
- #endif
- }
- // inline ll mul(ll a,ll b){ll d=(ll)(a*(double)b/mod+0.5);ll ret=a*b-d*mod;if (ret<0) ret+=mod;return ret;}
- }
- using namespace my_std;
- ll ksm(ll x,int y)
- {
- ll ret=1;
- for (;y;y>>=1,x=x*x%mod) if (y&1) ret=ret*x%mod;
- return ret;
- }
- ll inv(ll x){return ksm(x,mod-2);}
- ll fac[sz],_fac[sz];
- void init(){fac[0]=_fac[0]=1;rep(i,1,sz-1) _fac[i]=inv(fac[i]=fac[i-1]*i%mod);}
- ll C(int n,int m){return n>=m&&m>=0?fac[n]*_fac[m]%mod*_fac[n-m]%mod:0;}
- int n,K;
- int a[sz],b[sz],r[sz];
- ll dp[sz][sz],f[sz];
- ll ans[sz];
- int main()
- {
- file();
- init();
- read(n,K);
- if ((n+K)&1) return puts("0"),0;
- K=(n+K)>>1;
- rep(i,1,n) read(a[i]);
- rep(i,1,n) read(b[i]);
- sort(a+1,a+n+1);sort(b+1,b+n+1);
- int c=0;
- rep(i,1,n)
- {
- while (c<n&&b[c+1]<a[i]) ++c;
- r[i]=c;
- }
- dp[0][0]=1;
- rep(i,1,n)
- rep(j,0,i)
- dp[i][j]=(dp[i-1][j]+(j?1ll*(r[i]-j+1)*dp[i-1][j-1]%mod:0ll))%mod;
- rep(i,0,n) f[i]=dp[n][i]*fac[n-i]%mod;
- drep(i,n,K)
- {
- ans[i]=f[i];
- rep(j,i+1,n) ans[i]=(ans[i]-ans[j]*C(j,i)%mod+mod)%mod;
- }
- cout<<ans[K];
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2946503.html