数数题整理
容斥原理
\[A_i=\{x:x\text{ has porperty } P_i\} \\ \left|\bigcup_{i=1}^n A_i\right|=\sum_{1\le i\le n}|A_i|-\sum_{1\le i\lt j\le n}|A_i\cap A_j|+\sum_{1\le i\lt j\lt k\le n}|A_i\cup A_j\cup A_k|-\cdots+(-1)^{n-1}|A_1\cap A_2\cap\cdots\cap A_n| \]有时容斥系数会是莫比乌斯函数 \(\mu(n)\)。
子集反演
\(S,T\) 都是集合。若
\[g(S)=\sum_{T\subseteq S}f(T) \] \[f(S)=\sum_{T\subseteq S}(-1)^{|S|-|T|}g(T) \]习题
UVA10325 The Lottery
补集转化：将都不能被 \(a_i\) 整除转化为全集减能被 \(a_i\) 整除，然后用容斥原理解决。
\(A_i=\{x:1\le x\le n,a_i\mid x\}\)
Code
#include
#include
typedef long long ll;
int n,m;
ll a[30];
ll lcm(ll a,ll b){
return a/std::__gcd(a,b)*b;
}
bool mian(){
if(scanf("%d%d",&n,&m)==EOF)return 0;
for(int i=1;i<=m;i++)
scanf("%lld",a+i);
ll ans=n;
for(int i=1;i<=(1<>j)&1){
_lcm=lcm(_lcm,a[j+1]);
if(_lcm>n)break;
}
if(__builtin_popcountll(i)%2==1)ans-=n/_lcm;
else ans+=n/_lcm;
}
printf("%lld\n",ans);
return 1;
}
int main(){
while(mian());
return 0;
}
UVA11806 Cheerleaders
补集转化：将四条边上都有人转化为全集有边上没人，然后用容斥原理解决。
\(A_i=\{x:\text{arrangement }x\text{ that satisfies there are }i\text{ sides which don't have person}\}\)
算 \(|A_i|\) 时枚举有哪些边上没人，那么相应的能放人的地方是一个矩形。然后用组合数计算即可。
Code
#include
#include
const int N=500;
const int P=int(1e6)+7;
int C[N+10][N+10];
void init(){
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])%P;
}
}
void mian(int tc){
int n,m,k;scanf("%d%d%d",&n,&m,&k);
int ans=0;
for(int msk=0;msk<=15;msk++){ // msk 表示哪些边上放人了
int x=n,y=m;
for(int i=0;i<4;i++)
if((msk>>i)&1){
if(i%2==0)x--;
else y--;
}
if(__builtin_popcount(msk)%2==0)
(ans+=C[x*y][k])%=P;
else (ans-=C[x*y][k])%=P;
}
printf("Case %d: %d\n",tc,(ans+P)%P);
}
int main(){
init();
int T;scanf("%d",&T);
for(int i=1;i<=T;i++)mian(i);
return 0;
}
SP6285 NGM2 - Another Game With Numbers
UVA10325 双倍经验。
SP4168 SQFREE - Square-free integers
没看出这个题怎么用容斥做。。
结论：\(\mu^2(i)=\sum_{d^2\mid i}\mu(d)\)。证明：
设 \(i\) 的因数中，最大的平方数是 \(q=p_1^{2\alpha_1}p_2^{2\alpha_2}\cdots p_k^{2\alpha_k}\)，则 \(d^2\mid i\Leftrightarrow d\mid\sqrt q\)
\[\sum_{d^2\mid i}\mu(d)=\sum_{d\mid\sqrt q}\mu(d)=[\sqrt q=1]=[q=1] \]\([q=1]\) 相当于 \(i\) 没有平方因数，也就是 \(\mu^2(i)=1\)。证毕。
于是我们来推式子：
\[\sum_{i=1}^n\mu^2(i)=\sum_{i=1}^n\sum_{d^2\mid i}\mu(d)=\sum_{d=1}^{\lfloor\sqrt n\rfloor}\mu(d)\sum_{i=1}^n[d^2\mid i]=\sum_{d=1}^{\lfloor\sqrt n\rfloor}\mu(d)\left\lfloor\frac n{d^2}\right\rfloor \]整除分块即可。时间复杂度 \(O(\sqrt[3]n)\)，证明：
复杂度即为不同的 \(\left\lfloor\frac n{d^2}\right\rfloor\) 的个数。
当 \(d\le\sqrt[3]n\) 时，显然最多有 \(\sqrt[3]{n}\) 个数。
当 \(d\gt\sqrt[3]n\) 时，\(\left\lfloor\frac n{d^2}\right\rfloor\lt\left\lfloor\frac n{(\sqrt[3]n)^2}\right\rfloor=\left\lfloor \sqrt[3]n\right\rfloor\)，最多 \(\sqrt[3]n\) 个数。
综上，最多有 \(2\sqrt[3]n\) 个数。证毕。
Code
#include
#include
#include
typedef long long ll;
const int N=1e7;
int prm[N+10],notPrm[N+10],totp,mu[N+10],smu[N+10];
void sieve(){
notPrm[1]=1,mu[1]=1;
for(int i=2;i<=N;i++){
if(!notPrm[i])prm[++totp]=i,mu[i]=-1;
for(int j=1;j<=totp&&i*prm[j]<=N;j++){
notPrm[i*prm[j]]=1;
if(i%prm[j]==0)break;
mu[i*prm[j]]=-mu[i];
}
}
for(int i=1;i<=N;i++)
smu[i]=smu[i-1]+mu[i];
}
void mian(){
ll n;scanf("%lld",&n);
ll ans=0;
for(ll l=1,r;l<=ll(sqrt(n));l=r+1){
r=std::min(ll(sqrt(n/(n/(l*l)))),ll(sqrt(n)));
ans+=1LL*(n/(l*l))*(smu[r]-smu[l-1]);
}
printf("%lld\n",ans);
}
int main(){
sieve();
int T;scanf("%d",&T);
while(T--)mian();
return 0;
}
P4318 完全平方数
二分答案之后就和上一个题一模一样。
Code
#include
#include
#include
typedef long long ll;
const int N=1e7;
int prm[N+10],notPrm[N+10],totp,mu[N+10],smu[N+10];
ll k;
void sieve(){
notPrm[1]=1,mu[1]=1;
for(int i=2;i<=N;i++){
if(!notPrm[i])prm[++totp]=i,mu[i]=-1;
for(int j=1;j<=totp&&i*prm[j]<=N;j++){
notPrm[i*prm[j]]=1;
if(i%prm[j]==0)break;
mu[i*prm[j]]=-mu[i];
}
}
for(int i=1;i<=N;i++)
smu[i]=smu[i-1]+mu[i];
}
bool check(ll x){
ll ans=0;
for(ll l=1,r;l<=ll(sqrt(x));l=r+1){
r=std::min(ll(sqrt(x/(x/(l*l)))),ll(sqrt(x)));
ans+=1LL*(x/(l*l))*(smu[r]-smu[l-1]);
}
return ans>=k;
}
void mian(){
scanf("%lld",&k);
ll l=1,r=10000000000LL,mid,ans=-1;
while(l<=r){
mid=(l+r)>>1;
if(check(mid))ans=mid,r=mid-1;
else l=mid+1;
}
printf("%lld\n",ans);
}
int main(){
sieve();
int T;scanf("%d",&T);
while(T--)mian();
return 0;
}
P3349 [ZJOI2016] 小星星
考虑暴力 dp：设 \(f_{u,x,S}\) 表示现在饰品中的 \(u\) 映射到了 \(x\)，以 \(u\) 为根的子树中用掉了的映射的集合为 \(S\) 时的答案。
（因为我们要做树形 dp，所以要设状态 \(u\)，因为映射到的数不能重复，所以要设 \(x,S\)）
转移方程如下（\(E\) 表示原来饰品的边集）：
\[f_{u,x,S}=\prod_{v\in\operatorname{son}(u)}\sum_{T\subseteq S}\sum_{y\in T,(x,y)\in E}f_{v,y,T} \]由于要枚举子集，时间复杂度为 \(\mathcal O(n^33^n)\)，过不了。
把枚举子集改成容斥：先枚举 \(S\)，然后钦定我们只能映射到集合 \(S\) 里的数，但是映射到的数可以重复。然后通过容斥解决答案会被算多的问题。
这样 dp 状态就可以去掉一维了：
\[f_{u,x}=\prod_{v\in\operatorname{son}(u)}\sum_{y\in S,(x,y)\in E}f_{v,y} \]时间复杂度降到了 \(\mathcal O(n^32^n)\)，可以通过。
Code
#include
#include
#include
typedef long long ll;
const int N=17;
int n,m,G[N+10][N+10],T[N+10][N+10];
ll f[N+10][N+10],ans;
void DFS(int u,int _fa,int msk){
for(int x=1;x<=n;x++)
if((msk>>(x-1))&1)
f[u][x]=1;
for(int v=1;v<=n;v++)
if(v!=_fa&&T[u][v]){
DFS(v,u,msk);
for(int x=1;x<=n;x++)
if((msk>>(x-1))&1){
ll sum=0;
for(int y=1;y<=n;y++)
if((msk>>(y-1))&1&&G[x][y])
sum+=f[v][y];
f[u][x]*=sum;
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int u,v;scanf("%d%d",&u,&v);
G[u][v]=G[v][u]=1;
}
for(int i=1;i>(x-1))&1)res+=f[1][x];
ans+=((n-__builtin_popcount(msk))&1)?-res:res;
}
printf("%lld\n",ans);
return 0;
}