首页 > 代码库 > [BZOJ 3622]已经没有什么好害怕的了

[BZOJ 3622]已经没有什么好害怕的了

2024-07-16 13:15:48   221人阅读

世萌萌王都拿到了，已经没有什么好害怕的了——    (作死)

笑看哪里都有学姐，真是不知说什么好喵~

话说此题是不是输 0 能骗不少分啊，不然若学姐赢了，那么有头的学姐还能叫学姐吗？  (作大死)

 

 

这题的数据就告诉我们这是赤裸裸的 dp ，不过要加个容斥而已

注意到我们可以算出一共需要 s 组满足糖果数 > 药片数

(在这里显然有个特判，即 n-k 为奇数时，答案一定为 0 )

我们将两个读入的数组排序

令 next[i] 表示最大的 j 满足 糖果[i]>药片[j]

令 f[i][j] 表示枚举到第 i 个糖果时，有 j 组糖果数 > 药片数，但剩下的情况是不考虑的

则 f[i][j]=f[i-1][j]+f[i-1][j-1]*(next[i]-j+1)

但若把 f[n][s] 直接输出是妥妥地 WA 因为会有这种情况出现:

糖果: a1，a2，a3

药片: b1，b2，b3

a1>b1  a2>b2  a3>b3

那么 ((a1，b1)，(a2，b2)，a3不明)  ((a1，b1)，(a3，b3)，a2不明) 就会被视为两种答案

可见我们要求出的是 f’[n][s] 表示 n 个糖果，有 s 组糖果数 > 药片数，剩下的都是药片数 > 糖果数

这里就要用容斥了


这个挺好理解的吧

(n-i)! 是枚举后面 n-i 可能的方案，f‘[n][j]*C(j, i) 表示 f[n][i] 中实际有 j 组药片数 > 糖果数却被计入 f[n][i] 的数量

f‘[n][s]就是答案了，总时间复杂度为 O(n2)

 

 1 #include <cstdio> 2 #include <algorithm> 3 const int mod=1000000009; 4 const int size=2048; 5  6 namespace IOspace 7 { 8     inline int getint() 9     {10         register int num=0;11         register char ch;12         do ch=getchar(); while (ch<‘0‘ || ch>‘9‘);13         do num=num*10+ch-‘0‘, ch=getchar(); while (ch>=‘0‘ && ch<=‘9‘);14         return num;15     }16     inline void putint(int num, char ch=‘\n‘)17     {18         char stack[15];19         register int top=0;20         if (num==0) stack[top=1]=‘0‘;21         for ( ;num;num/=10) stack[++top]=num%10+‘0‘;22         for ( ;top;top--) putchar(stack[top]);23         if (ch) putchar(ch);24     }    25 }26 27 int n, k;28 int a[size], b[size];29 int next[size];30 int fact[size];31 int C[size][size];32 int f[size][size];33 inline int add(int x, int y) {return (x+y)%mod;}34 inline int sub(int x, int y) {return (x-y+mod)%mod;}35 inline int mul(int x, int y) {return static_cast<long long>(x)*y%mod;}36 inline void prepare();37 38 int main()39 {40     n=IOspace::getint(), k=IOspace::getint();41     if ((n-k)&1) {putchar(‘0‘); putchar(‘\n‘); return 0;}42     k=(n+k)>>1;43     for (int i=1;i<=n;i++) a[i]=IOspace::getint();44     for (int i=1;i<=n;i++) b[i]=IOspace::getint();45 46     prepare();47 48     f[0][0]=1;49     for (int i=1;i<=n;i++)50         for (int j=0;j<=i;j++)51         {52             f[i][j]=f[i-1][j];53             if (j && next[i]-j+1>0)54                 f[i][j]=add(f[i][j], mul(f[i-1][j-1], next[i]-j+1));55         }56 57     for (int i=n;i>=k;i--)58     {59         f[n][i]=mul(f[n][i], fact[n-i]);60         for (int j=i+1;j<=n;j++) f[n][i]=sub(f[n][i], mul(f[n][j], C[j][i]));61     }62 63     IOspace::putint(f[n][k]);64 65     return 0;66 }67 inline void prepare()68 {69     std::sort(a+1, a+n+1); std::sort(b+1, b+n+1);70 71     int j=0;    72     for (int i=1;i<=n;i++)73     {74         for ( ;j<n && a[i]>b[j+1];j++);75         next[i]=j;76     }77 78     for (int i=0;i<=n;i++)79     {80         C[i][0]=C[i][i]=1;81         for (int j=1;j<i;j++)82             C[i][j]=add(C[i-1][j-1], C[i-1][j]);83     }84 85     fact[0]=1;86     for (int i=1;i<=n;i++) fact[i]=mul(fact[i-1], i);87 }
本傻装B系列

 

 

『——真不简单呢。不过，已经没有什么好害怕的了。』  (作死作死作死作死作死作死作死作死作死作死作死作死作死)

 


联系
我们