数学2（容斥原理）

P3197 [HNOI2008] 越狱

发生越狱的状态数=总状态数-不越狱的状态数， 很显然总状态数为 $m^n$， 而不越狱的状态数应该是同样宗教互不相邻， 第一个房间有 $m$ 种，其他房间都是 $m-1$ 种， 所以状态数应该是 $m\mathrm{·}(m-1{)}^{n-1}$。 答案：$m^n-m\mathrm{·}(m-1{)}^{n-1}$ 代码：

#include
using namespace std;
#define int long long
const int mod=100003;
int m,n;
int mi(int x,int y){
    int ans=1;
    while(y){
        if(y%2) ans*=x,ans%=mod;
        y/=2,x=x*x%mod;
    }
    return ans;
}
signed main(){
	cin>>m>>n;
	cout

`#include
using namespace std;
#define int long long
const int mod=100003;
int m,n;
int mi(int x,int y){
    int ans=1;
    while(y){
        if(y%2) ans*=x,ans%=mod;
        y/=2,x=x*x%mod;
    }
    return ans;
}
signed main(){
	cin>>m>>n;
	coutmi(m,n)-m*mi(m-1,n-1)%mod+mod)%mod;
	return 0;
}`

P8557 炼金术（Alchemy）

显而易见，对于每一种矿物，至少需要分配到一个熔炉， 方案数为总集减去空集，即 $2^k-1$。 而一共有 $n$ 个矿物，每个矿物有 $2^k-1$种方案， 所以答案就是 $(2^k-1{)}^n$ 代码：

#include
using namespace std;
#define int long long
const int mod=998244353;
int n,k;
int mi(int x,int y){
    int ans=1;
    while(y){
        if(y%2) ans*=x,ans%=mod;
        y/=2,x=x*x%mod;
    }
    return ans%mod;
}
signed main(){
	cin>>n>>k;
	cout

`#include
using namespace std;
#define int long long
const int mod=998244353;
int n,k;
int mi(int x,int y){
    int ans=1;
    while(y){
        if(y%2) ans*=x,ans%=mod;
        y/=2,x=x*x%mod;
    }
    return ans%mod;
}
signed main(){
	cin>>n>>k;
	coutmi((mi(2,k)-1),n);
	return 0;
}`

P6298 齿轮

首先统计每个齿数的出现频率 $t\left[x\right]$， 并预处理组合数 $\left(\genfrac{}{}{0ex}{}{n}{k}\right)\text{[PARSE ERROR: Undefined("Command("bmod")")]}M$ 用于快速计算。 接着对于每个数 $i$， 统计所有齿数为 $i$ 的倍数的齿轮个数 $f\left[i\right]=\sum _{j=i,2i,\text{[PARSE ERROR: Undefined("Command("dots")")]}}^{j\text{[PARSE ERROR: Undefined("Command("le")")]}m}t\left[j\right]$， 这表示最大公约数是 $i$ 的倍数的候选齿轮数。 然后利用容斥原理，从大到小计算 $ans\left[i\right]=\left(\genfrac{}{}{0ex}{}{f\left[i\right]}{k}\right)-\sum _{j=2}^{\lfloor m/i\rfloor }ans[i·j]$， 这样 $ans\left[i\right]$ 就表示最大公约数恰好为 $i$ 的方案数。 最后输出 $ans\left[1\right]$ 到 $ans\left[m\right]$ 即为所有损耗因子的答案。 代码：

#include
using namespace std;
#define int long long
const int N=1e6+5;
const int mod=1e9+7;
int n,m,k;
int a[N],ans[N],t[N],f[N],j[N],jj[N];

int mi(int x,int y){
    int ans=1;
    while(y){
        if(y%2) ans*=x,ans%=mod;
        y/=2,x=x*x%mod;
    }
    return ans;
}

int C(int x,int y){
    if(xy) return 0;
    return j[y]*jj[x]%mod*jj[y-x]%mod;
}

signed main(){
    cin>>n>>m>>k;
    for(int i=1;i>a[i];
        t[a[i]]++;
    }
    j[0]=jj[0]=1;
    for(int i=1;i=1;i--){
        ans[i]=C(k,f[i]);
        for(int j=i*2;j

`#include
using namespace std;
#define int long long
const int N=1e6+5;
const int mod=1e9+7;
int n,m,k;
int a[N],ans[N],t[N],f[N],j[N],jj[N];

int mi(int x,int y){
    int ans=1;
    while(y){
        if(y%2) ans*=x,ans%=mod;
        y/=2,x=x*x%mod;
    }
    return ans;
}

int C(int x,int y){
    if(x0||y0||x>y) return 0;
    return j[y]*jj[x]%mod*jj[y-x]%mod;
}

signed main(){
    cin>>n>>m>>k;
    for(int i=1;i
        cin>>a[i];
        t[a[i]]++;
    }
    j[0]=jj[0]=1;
    for(int i=1;i
        j[i]=j[i-1]*i%mod;
        jj[i]=mi(j[i],mod-2);
    }
    for(int i=1;i
        for(int j=i;j
            f[i]+=t[j];
        }
    }
    for(int i=m;i>=1;i--){
        ans[i]=C(k,f[i]);
        for(int j=i*2;j
            ans[i]=(ans[i]-ans[j]+mod)%mod;
        }
    }
    for(int i=1;ians[i]" ";
    return 0;
}`