数学2（容斥原理） P3197 [HNOI2008] 越狱 发生越狱的状态数=总状态数-不越狱的状态数， 很显然总状态数为 m^n， 而不越狱的状态数应该是同样宗教互不相邻， 第一个房间有 m 种，其他房间都是 m-1 种， 所以状态数应该是 m·(m-1)^{n-1}。 答案：m^n-m·(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[x]， 并预处理组合数 \binom{n}{k} \bmod M 用于快速计算。 接着对于每个数 i， 统计所有齿数为 i 的倍数的齿轮个数 f[i] = \sum_{j=i, 2i, \dots}^{j \le m} t[j]， 这表示最大公约数是 i 的倍数的候选齿轮数。 然后利用容斥原理，从大到小计算 ans[i] = \binom{f[i]}{k} - \sum_{j=2}^{\lfloor m/i \rfloor} ans[i \cdot j]， 这样 ans[i] 就表示最大公约数恰好为 i 的方案数。 最后输出 ans[1] 到 ans[m] 即为所有损耗因子的答案。 代码： #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; }`
容斥原理
笔记