相关链接
解题报告:http://www.lydsy.com/JudgeOnline/problem.php?id=3622
解题报告
恰好有$k$个条件满足,这不就是广义容斥原理吗?
不知道广义容斥原理的同学可以去找$sengxian$要他的$PDF$看哦!
知道广义容斥原理的同学,这题难点就是求$\alpha(i)$
设$f_{i,j}$表示考虑了前$i$个糖果,至少有$j$个糖果符合条件的方案数
那么$\alpha(i)=f_{n,i} \cdot (n-i)!$
于是先$O(n^2)$DP出$\alpha(i)$
然后根据广义容斥原理$O(n)$推出$\beta(k)$就可以了
总时间复杂度:$O(n^2)$
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 2009; const int MOD = 1000000009; int n,K,a[N],b[N],sum[N],fac[N],alpha[N],f[N][N],C[N][N]; inline int read() { char c=getchar(); int f=1,ret=0; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret * f; } int main() { n = read(); K = read(); if ((n + K) & 1) { puts("0"); exit(0); } K = n + K >> 1; for (int i=1;i<=n;i++) { a[i] = read(); } sort(a+1, a+1+n); for (int i=1;i<=n;i++) { b[i] = read(); } sort(b+1, b+1+n); for (int i=1,j=0;i<=n;i++) { for (;j < n && b[j+1] < a[i];++j); sum[i] = j; } 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; } } fac[0] = 1; for (int i=1;i<=n;i++) { fac[i] = fac[i-1] * (LL)i % MOD; } f[0][0] = 1; for (int i=1;i<=n;i++) { for (int j=0;j<=i;j++) { f[i][j] = (f[i-1][j] + (j?f[i-1][j-1] * max(0ll, (sum[i] - j + 1ll)):0ll)) % MOD; } } for (int i=0;i<=n;i++) { alpha[i] = (LL)f[n][i] * fac[n - i] % MOD; } int ans = 0; for (int i=K,t=1;i<=n;i++,t*=-1) { ans = (ans + (LL)alpha[i] * C[i][K] * t) % MOD; } printf("%d\n",(ans+MOD)%MOD); return 0; }
An impressive share, I just given this onto a colleague who was doing a little analysis on this. And he in fact bought me breakfast because I found it for him.. smile. So let me reword that: Thnx for the treat! But yeah Thnkx for spending the time to discuss this, I feel strongly about it and love reading more on this topic. If possible, as you become expertise, would you mind updating your blog with more details? It is highly helpful for me. Big thumb up for this blog post!
Rattling clean website , thanks for this post.