3622: 已经没有什么好害怕的了
Time Limit: 10
Sec Memory Limit: 256 MB
Description
已经使Modoka有签订契约，和自己一起战斗的想法后，Mami忽然感到自己不再是孤单一人了呢。
于是，之前的谨慎的战斗作风也消失了，在对Charlotte的傀儡使用终曲——Tiro Finale后，Mami面临着即将被Charlotte的本体吃掉的局面。
这时，已经多次面对过Charlotte的Homura告诉了学OI的你这样一个性质——Charlotte的结界中有两种具有能量的元素——一种是“糖果”，另一种是“药片”，每种各有n个。在Charlotte发动进攻前，“糖果”和“药片”会两两配对，若恰好“糖果”比“药片”能量大的组数比“药片”比“糖果”能量大的组数多k组，则在这种局面下，Charlotte的攻击会丢失，从而Mami仍有消灭Charlotte的可能。你必须根据Homura告诉你的“糖果”和“药片”的能量的信息迅速告诉Homura这种情况的个数。
于是，之前的谨慎的战斗作风也消失了，在对Charlotte的傀儡使用终曲——Tiro Finale后，Mami面临着即将被Charlotte的本体吃掉的局面。
这时，已经多次面对过Charlotte的Homura告诉了学OI的你这样一个性质——Charlotte的结界中有两种具有能量的元素——一种是“糖果”，另一种是“药片”，每种各有n个。在Charlotte发动进攻前，“糖果”和“药片”会两两配对，若恰好“糖果”比“药片”能量大的组数比“药片”比“糖果”能量大的组数多k组，则在这种局面下，Charlotte的攻击会丢失，从而Mami仍有消灭Charlotte的可能。你必须根据Homura告诉你的“糖果”和“药片”的能量的信息迅速告诉Homura这种情况的个数。
Input
第一行两个整数n,k，含义如题目描述。
接着第二行n个整数，第i个数表示第i个糖果的能量。
第三行n个整数，第j个数表示第j个药片的能量。
接着第二行n个整数，第i个数表示第i个糖果的能量。
第三行n个整数，第j个数表示第j个药片的能量。
Output
一个整数，表示消灭Charlotte的情况个数。答案可能会很大,所以mod (109+9)
Sample Input
4 2
5 35 15
45
40 20 10
30
Sample Output
4
HINT
对于100%的数据：1<=n<=2000，0<=k<=n
输入的2*n个数字保证全不相同。
输入的2*n个数字保证全不相同。
Solution
“糖果”比“药片”能量大的组数比“药片”比“糖果”能量大的组数多k组意味着“糖果”比“药片”的能量大的组数为${n+k}/2$，下文中为了方便，仍然将这个量用k表示。用赋值语句表达就是k=(n+k)/2。
本题询问的是恰好，我们仍然需要将其转换为至少。
我们约定，所有的糖果的的能量用数组a表示，所有的药片的能量用数组b表示。将a中的元素和b中的元素组成有序对的过程称为配对，a、b被称为已配对的元素；反之，a、b被称为闲置元素若干有序对组成的数组用p表示，对于pi∈p，若pi.a>pi.b，则称a、b匹配，这个有序对被称为合法的；反之，将其为非法的。设S是有序对的集合，再设S’是S中所有合法有序对的集合，显然S’ ⊆S。若S满足：1、card(S)=n；2、card(S’)=k；则S被称为合法的。设T是全体合法S的集合，则card(T)即为所求。
记dp1[i][j]表示数组a的前i个元素与j个数组b中的元素（不一定是前i个）匹配的方案数。对于每一个新加入的a[i]，我们有两种方式处理：1、将a[i]闲置，不与闲置的b的元素配对；2、将a[i]与一个闲置的b[i]配对，而可配对的方案数为所有可以与a[i]配对的b的元素的数量减已配对的b的元素的数量（为了保证所有已配对的b的元素一定可以与a[i]配对，我们将a从小到大排序）。我们用match[i]表示可以与a[i]配对的b数组的元素的数量，于是得到：dp1[i][j]=dp1[i-1][j]+dp1[i-1][j-1]×max(0,match[i]-(j-1))。实现如下：
本题询问的是恰好，我们仍然需要将其转换为至少。
我们约定，所有的糖果的的能量用数组a表示，所有的药片的能量用数组b表示。将a中的元素和b中的元素组成有序对的过程称为配对，a、b被称为已配对的元素；反之，a、b被称为闲置元素若干有序对组成的数组用p表示，对于pi∈p，若pi.a>pi.b，则称a、b匹配，这个有序对被称为合法的；反之，将其为非法的。设S是有序对的集合，再设S’是S中所有合法有序对的集合，显然S’ ⊆S。若S满足：1、card(S)=n；2、card(S’)=k；则S被称为合法的。设T是全体合法S的集合，则card(T)即为所求。
记dp1[i][j]表示数组a的前i个元素与j个数组b中的元素（不一定是前i个）匹配的方案数。对于每一个新加入的a[i]，我们有两种方式处理：1、将a[i]闲置，不与闲置的b的元素配对；2、将a[i]与一个闲置的b[i]配对，而可配对的方案数为所有可以与a[i]配对的b的元素的数量减已配对的b的元素的数量（为了保证所有已配对的b的元素一定可以与a[i]配对，我们将a从小到大排序）。我们用match[i]表示可以与a[i]配对的b数组的元素的数量，于是得到：dp1[i][j]=dp1[i-1][j]+dp1[i-1][j-1]×max(0,match[i]-(j-1))。实现如下：
for (int i = 1; i <= n;
i++)
{
match[i] = lower_bound(b + 1, b + n + 1, a[i]) - b
- 1;
}
dp1[0][0] = 1;
for (int i = 1; i <= n;
i++)
{
dp1[i][0] =
dp1[i - 1][0];
for (int j = 1; j <=
n; j++)
{
//a[i]不与新的b匹配，a[i]与一个可以匹配但未匹配的b匹配
dp1[i][j] =
(dp1[i - 1][j] + dp1[i - 1][j - 1] * max<long long>(0,
(match[i] - j + 1))) % mod;
}
}
这样dp1[n][i]是不是就表示含义至少i个合法对的方案数呢？
答案是否定的。在dp1[n][i]中，我们认为a、b中分别只有i个元素是已配对，剩余的元素是闲置的，今令剩余的a、b中剩余的元素自由配对，得到的对可能合法也可能非法，自由配对的方案数为(n-i)!。
我们引入数组dp2，dp2[i]表示存在至少i个有序的对的集合S的数量。根据上一段的分析，dp2[i]=dp1[n][i]×(n-i)!。实现如下：
答案是否定的。在dp1[n][i]中，我们认为a、b中分别只有i个元素是已配对，剩余的元素是闲置的，今令剩余的a、b中剩余的元素自由配对，得到的对可能合法也可能非法，自由配对的方案数为(n-i)!。
我们引入数组dp2，dp2[i]表示存在至少i个有序的对的集合S的数量。根据上一段的分析，dp2[i]=dp1[n][i]×(n-i)!。实现如下：
for (int i = 0; i <= n;
i++)
{
//已匹配的b保持现状，剩下的未配对的b与剩余的a“自由组合”
dp2[i] = fact[n
- i] * dp1[n][i] % mod;
}
如何将“至少”转换为恰好呢？参考BZOJ 1879的解法，我们容易想到dp2[i]实际上可以看作若干个用状压表示的状态的和。设dp3[i]表示至少有某些b中的元素匹配已匹配的方案数，有些晦涩，我们举例说明：dp3[1001]表示满足至少存在b[1]、b[4]已经匹配的集合S的数量。我们有：dp2[2]=dp3[1001]+dp3[1010]+dp3[1100]+dp3[0101]+dp3[0110]+dp3[0011]。概况地说就是dp2[i]=Σdp3[j], where count1(j)=i。引入状压后我们便会发现，加入k=2，n=4，答案便来自dp3[1001]、dp3[1010]、dp3[1100]、dp3[0101]、dp3[0110]、dp3[0011]，已dp3[1001]为例，满足恰好有k个合法对的方案数为dp3[1001]-dp3[1101]-dp3[1011]+dp3[1111]，如图所示：
而对于状态dp3[1101]，在计算dp3[1001]、dp3[1100]、dp[0101]三个状态时它都会被减去，重复计算C(3,2)=3次（从状态1101的三个一中取出2个）。归纳可以得到dp2[3]也应该被减去C(3,2)次，推广可得dp2[i]将被加上或减去C(i,k)次。即：$$ans=∑↙{i=k}↖n (-1)^{i-k}C_i^kdp2_i$$
实现如下：
long long ans = 0;
for (int i = k; i <= n;
i++)
{
if ((i - k + 1)
& 1)
{
ans = (ans +
c[i][k] * dp2[i]) % mod;
else
{
ans = (ans -
c[i][k] * dp2[i] % mod + mod) % mod;
}
}
事实上，我们解此题用到的方法叫做“二项式反演”，表述如下： $$a_k=∑↙{i=k}↖n(\table i;k)b_i⇒b_k=∑↙{i=k}↖n(-1)^{i-k}(\table i;k)a_i$$
Code
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const long long mod =
1000000009;
inline void read(int &x)
{
x = 0; char ch = getchar(); bool f = 0;
while (ch>'9' || ch<'0') { if (ch == '-')f = 1; ch = getchar(); }
while (ch >= '0'&&ch
<= '9') { x = x * 10 + ch - 48; ch = getchar();
}
if (f)x = -x;
}
inline void read(long long &x)
{
x = 0; char ch = getchar(); bool f = 0;
while (ch>'9' || ch<'0') { if (ch == '-')f = 1; ch = getchar(); }
while (ch >= '0'&&ch
<= '9') { x = x * 10 + ch - 48; ch = getchar();
}
if (f)x = -x;
}
long long a[2001], b[2001];
//match[i]——第i个a可以与多少b匹配
long long match[2001];
//dp1[i][j]——前i个a与j个b匹配的方案数 (剩下的b可能匹配也可能不匹配）
long long dp1[2001][2001];
//dp2[i]——有至少i个匹配的方案数
long long dp2[2001];
//n!
long long fact[2001];
//组合数
long long c[2001][2001];
int main()
{
int n, k;
read(n); read(k);
k = n + k;
if (k & 1)
{
puts("0");
return 0;
}
k >>= 1;
fact[0] = 1;
for (int i = 1; i <=
n; i++)
{
fact[i] =
fact[i - 1] * i%mod;
}
c[0][0] = 1;
for (int i = 1; i <=
n; i++)
{
c[i][0] = 1;
for (int j = 1; j <=
i; j++)
{
c[i][j]
= (c[i - 1][j] + c[i - 1][j - 1]) % mod;
}
}
for (int i = 1; i <=
n; i++)
{
read(a[i]);
}
for (int j = 1; j <=
n; j++)
{
read(b[j]);
}
sort(a + 1, a + n + 1);
sort(b + 1, b + n + 1);
for (int i = 1; i <=
n; i++)
{
match[i] = lower_bound(b + 1, b + n + 1, a[i]) - b
- 1;
}
dp1[0][0] = 1;
for (int i = 1; i <=
n; i++)
{
dp1[i][0] =
dp1[i - 1][0];
for (int j = 1; j <=
n; j++)
{
//a[i]不与新的b匹配，a[i]与一个可以匹配但未匹配的b匹配
dp1[i][j]
= (dp1[i - 1][j] + dp1[i - 1][j - 1] * max<long long>(0,
(match[i] - j + 1))) % mod;
}
}
for (int i = 0; i <=
n; i++)
{
//已匹配的b保持现状，剩下的未配对的b与剩余的a“自由组合”
dp2[i] =
fact[n - i] * dp1[n][i] % mod;
}
long long ans = 0;
for (int i = k; i <=
n; i++)
{
if ((i - k + 1)
& 1)
{
ans =
(ans + c[i][k] * dp2[i]) % mod;
}
else
{
ans =
(ans - c[i][k] * dp2[i] % mod + mod) % mod;
}
}
cout << ans << endl;
return 0;
}
没有评论:
发表评论