bzoj 题目链接 (权限题)
前置知识: 广义容斥原理 https://www.cnblogs.com/hbyer/p/10026456.html
考虑对于每个方案作为一个元素, 每一位相同作为一个性质.
考虑在 \(n?\) 个里选 \(x?\) 个, 要满足这 \(x?\) 个性质, 即集合中有 \(x?\) 个相同, 剩下 \(n-x?\) 个集合里的元素可选可不选, 但是不能都不选, 要减去空集的一个, 注意这里的集合指的是题目中的集合,
所以可得:
\[ \alpha (x) = \binom{n}{x} (2^{2^{n-x}}-1) \]
然后设 \(\beta (x)\) 为恰好有 x 个性质的元素个数, 可得:
\[ \beta(x) = \sum _{i=x} ^{n} (-1)^{i-x}\binom{i}{x} \alpha(i) \]
答案为 \(\beta (k)\).
- #include<bits/stdc++.h>
- using namespace std;
- #define int long long
- void read(int &x) {
- x=0;int f=1;char ch=getchar();
- for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
- for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
- }
- void print(int x) {
- if(x<0) x=-x,putchar('-');
- if(!x) return ;print(x/10),putchar(x%10+'0');
- }
- void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}
- #define maxn 1000050
- #define mod 1000000007
- int n,fac[maxn],ifac[maxn],f[maxn],k;
- int qpow(int a,int x) {
- int res=1;
- for(;x;x>>=1,a=a*a%mod) if(x&1) res=res*a%mod;
- return res;
- }
- signed main() {
- read(n),read(k);f[0]=2,fac[0]=ifac[0]=1;
- for(int i=1;i<=n;i++) f[i]=f[i-1]*f[i-1]%mod,fac[i]=fac[i-1]*i%mod;
- ifac[n]=qpow(fac[n],mod-2);
- for(int i=n-1;i>=0;i--) ifac[i]=ifac[i+1]*(i+1)%mod;
- int ans=0;
- for(int op=-1,i=k;i<=n;i++) {
- op=-op;
- ans=(ans+op*fac[n]*ifac[i]%mod*ifac[n-i]%mod*(f[n-i]-1)%mod*fac[i]%mod*ifac[k]%mod*ifac[i-k]%mod)%mod;
- }
- write((ans%mod+mod)%mod);
- return 0;
- }
[bzoj2893] 集合计数
来源: http://www.bubuko.com/infodetail-2863493.html