好我放弃了多项式到时候再说吧。
Min-Max 容斥
直接上式子：
\[\max(S)=\sum_{T\subseteq S}(-1)^{|T|+1}\min(T) \]这个 \(\min\) 和 \(\max\) 是可以互换的。形式十分好背，证明不管。
这玩意的用处主要是求期望，因为在期望下这玩意也成立。可以把覆盖一个集合中的所有元素变成第一次覆盖一个元素。
没什么好说的，直接上题。
[HAOI2015]按位或
回来看一眼这玩意居然紫了。
显然可以把每一位单独考虑，全集为所有二进制位。设 \(E(\max(S))\) 是 \(S\) 中的位都变为 \(1\) 的期望步数，那么
\[E(\max(S))=\sum_{T\subseteq S}(-1)^{|T|+1}\min(T) \]考虑怎么求出 \(\min(T)\)。设选了 \(T\) 补集的子集的概率为 \(p\)，那么走 \(n\) 步的概率就是
\[p^{n-1}(1-p) \]所以
\[\min(T)=(1-p)\sum_{k=1}kp^{k-1} \]后边是等差乘等比，错位相减得到结果是 \(\frac 1{1-p}\)。于是有 \(\min(T)=\frac 1{1-p}\)。\(p\) 很好求，就是个子集和，FWT 即可。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int n;
double a[1<<20],ans;
const double eps=1e-9;
void getor(double a[],int n,int tp){
for(int mid=1;mid<n;mid<<=1){
for(int i=0;i<n;i+=(mid<<1)){
for(int j=0;j<mid;j++){
a[i+j+mid]=a[i+j+mid]+a[i+j]*tp;
}
}
}
}
int main(){
scanf("%d",&n);
const int u=(1<<n)-1;
for(int i=0;i<(1<<n);i++)scanf("%lf",&a[i]);
getor(a,1<<n,1);
for(int i=1;i<(1<<n);i++){
int ret=__builtin_popcount(i)+1;
if((1.0-a[u^i])<=eps){
puts("INF");return 0;
}
double tmp=1.0/(1.0-a[u^i]);
if(ret&1)ans-=tmp;
else ans+=tmp;
}
printf("%.9lf\n",ans);
return 0;
}
[BZOJ4833]最小公倍佩尔数
首先打几个数的表或者推一下式子可以发现规律
\[e(n)=e(n-1)+2f(n-1)\qquad\qquad f(n)=e(n-1)+f(n-1) \]那么
\[\begin{aligned} e(n)-f(n)=f(n-1)\\ f(n)=e(n-1)+f(n-1)\\ f(n)=2f(n-1)+f(n-2) \end{aligned} \]初值 \(f(0)=0,f(1)=1\)。
然后考虑计算 \(g(n)\)。由于 \(\text{lcm}\) 是对每个质因子取 \(\max\)，那么枚举每个质因子，使用 Min-Max 容斥，就有
\[\begin{aligned} \prod_pp^{\max(S)}=\prod_pp^{\sum_{T\subseteq S}(-1)^{|T|+1}\min(T)}\\ \text{lcm}(S)=\prod_{T\subseteq S}\gcd(T)^{(-1)^{|T|+1}} \end{aligned} \]那么
\[g(n)=\prod_{T\subseteq S}f_{\gcd(T)}^{(-1)^{|T|+1}}=\prod_{i=1}^nf_i^{\sum_{T\subseteq S}[\gcd(T)=i](-1)^{|T|+1}} \]上边那一堆指数假设是 \(a_i\)，那么设 \(b_i=\sum_{i|d}a_d\)，那么 \(a_i=\sum_{i|d}\mu(\frac di)b_d\)。代入原式：
\[\begin{aligned} g_n&=\prod_{i=1}^nf_i^{a_i}\\ &=\prod_{i=1}^nf_i^{\sum_{i|d}\mu(\frac di)b_d}\\ &=\prod_{i=1}^n\prod_{i|d}f_i^{\mu(\frac di)b_d} \end{aligned} \]算一下 \(b_i\)。发现 \(b_i=\sum_{T\subseteq S}[i|\gcd(T)](-1)^{|T|+1}\)，而 \(S\) 就是 \(1-n\) 的数，所以
\[b_i=\sum_{i=1}^{2^{\lfloor \frac ni\rfloor}-1}(-1)^{i+1}=1 \]\(O(n\log n)\) 算就行了。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
int n,ans,mod,p[1000010],miu[1000010],f[1000010],g[1000010],inv[1000010];
bool v[1000010];
int qpow(int a,int b){
int ans=1;
while(b){
if(b&1)ans=1ll*ans*a%mod;
a=1ll*a*a%mod;
b>>=1;
}
return ans;
}
void get(int n){
miu[1]=1;
for(int i=2;i<=n;i++){
if(!v[i])miu[i]=-1,p[++p[0]]=i;
for(int j=1;j<=p[0]&&i*p[j]<=n;j++){
v[i*p[j]]=true;
if(i%p[j]==0)break;
miu[i*p[j]]=-miu[i];
}
}
}
int main(){
int tim;scanf("%d",&tim);
get(1000000);
while(tim--){
scanf("%d%d",&n,&mod);f[1]=1;ans=0;
for(int i=2;i<=n;i++)f[i]=(2ll*f[i-1]+f[i-2])%mod;
for(int i=1;i<=n;i++)g[i]=1,inv[i]=qpow(f[i],mod-2);
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j+=i){
if(miu[j/i]==1)g[j]=1ll*g[j]*f[i]%mod;
else if(miu[j/i]==-1)g[j]=1ll*g[j]*inv[i]%mod;
}
}
g[0]=1;
for(int i=1;i<=n;i++)g[i]=1ll*g[i-1]*g[i]%mod,ans=(ans+1ll*i*g[i])%mod;
printf("%d\n",ans);
}
return 0;
}
[PKUWC2018]随机游走
一看就是 Min-Max 容斥。然后我们需要知道从 \(x\) 出发经过每个点集一个点的期望步数。有一个 dp：设 \(dp_{i,S}\) 为在点 \(i\) ，点集为 \(S\) 的期望步数，那么：
\[dp_{i,S}= \begin{cases} 0，\qquad&i\in S\\ 1+\frac 1{d_i}\sum_{v}dp_{v,S},\qquad &\text{otherwise} \end{cases} \]考虑一下后边那个式子。这时候高斯消元直接死了。事实上对于转移在一个环上的这种，我们有个操作叫系数递推。
首先把父亲和儿子的贡献分开。
\[dp_{i,S}=1+\frac 1{d_i}dp_{fa_i,S}+\frac 1{d_i}\sum_{son}dp_{son_i,S} \]设 \(dp_{i,S}=k_idp_{fa_i,S}+b_i\)。那么将和这个式子无关的项，也就是所有儿子换成这个式子：
\[dp_{i,S}=1+\frac 1{d_i}dp_{fa_i,S}+\frac 1{d_i}\sum_{son}k_{son}dp_{i,S}+b_{son}\\ (d_i-\sum_{son}k_{son})dp_{i,S}=dp_{fa_i,S}+\sum_{son}b_{son}+d_i\\ k_i=\frac 1{d_i-\sum_{son}k_{son}}\qquad\qquad b_i=\frac{d_i+\sum_{son}b_{son}}{d_i-\sum_{son}k_{son}} \]这玩意和父亲没有关系，递推就行了。然后我们只需要根的，那根没有父亲，就是 \(b_x\)。预处理后可以达到 \(O(n2^n+q2^n)\)。应该能过。
事实上我们发现每次 Min-Max 容斥就是一个带了系数的子集和，而且这个系数还是不变的。所以预处理后直接乘上系数然后 FWT 就能 \(O(n2^n+q)\) 了。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int mod=998244353;
int n,q,rt,a[20],b[20],dp[1<<18],d[20];
int qpow(int a,int b){
int ans=1;
while(b){
if(b&1)ans=1ll*ans*a%mod;
a=1ll*a*a%mod;
b>>=1;
}
return ans;
}
struct node{
int v,next;
}edge[50];
int t,head[20];
void add(int u,int v){
edge[++t].v=v;edge[t].next=head[u];head[u]=t;
}
void dfs(int x,int f,int s){
int suma=0,sumb=0;
if(s&(1<<(x-1)))return;
for(int i=head[x];i;i=edge[i].next){
if(edge[i].v!=f){
dfs(edge[i].v,x,s);
suma+=a[edge[i].v];sumb+=b[edge[i].v];
}
}
a[x]=qpow((d[x]-suma+mod)%mod,mod-2);
b[x]=1ll*a[x]*(d[x]+sumb)%mod;
}
void getor(int a[],int n,int tp){
for(int mid=1;mid<n;mid<<=1){
for(int i=0;i<n;i+=(mid<<1)){
for(int j=0;j<mid;j++){
a[i+j+mid]=(a[i+j+mid]+1ll*a[i+j]*tp)%mod;
}
}
}
}
int main(){
scanf("%d%d%d",&n,&q,&rt);
for(int i=1;i<n;i++){
int u,v;scanf("%d%d",&u,&v);
add(u,v);add(v,u);d[u]++;d[v]++;
}
for(int i=1;i<(1<<n);i++){
for(int j=1;j<=n;j++)a[j]=b[j]=0;
dfs(rt,0,i);
dp[i]=(b[rt]*((__builtin_popcount(i)+1&1)?-1:1)+mod)%mod;
}
getor(dp,1<<n,1);
while(q--){
int k,s=0;scanf("%d",&k);
for(int i=1;i<=k;i++){
int x;scanf("%d",&x);s|=1<<(x-1);
}
printf("%d\n",dp[s]);
}
return 0;
}
扩展 Min-Max 容斥
对于第 \(k\) 大，我们也有：
\[Kth\max(S)=\sum_{T\subseteq S}(-1)^{|T|-k}\binom{|T|-1}{k-1}\min(T) \]这玩意也是可以 \(\max\) 和 \(\min\) 互换。在期望意义下同样成立。
P4707 重返现世
好神。
首先题目要的是 \(Kth\min\)，先变成 \(Kth\max\)。那么 \(k\) 就变成了 \(n-k+1\)。把式子搬出来：
\[E(Kth\max(S))=\sum_{T\subseteq S}(-1)^{|T|-k}\binom{|T|-1}{k-1}E(\min(T)) \]\(E(\min(T))\) 是好求的，就是 \(\frac m{\sum_{i\in T}p_i}\)。
然而 \(n\) 是 \(1000\)，枚举子集又直接死了。看上去只能 \(dp\)。
首先肯定要枚举第 \(i\) 个物品，然后考虑一下剩下的状态怎么设计。发现这题 \(m\) 只有 \(10000\)，所以或许可以把这玩意扔到状态里边。
设 \(dp_{i,j,k}\) 是前 \(i\) 个物品选 \(j\) 个，\(\sum p_i=k\) 的方案数，显然有 \(dp_{i,j,k}=dp_{i-1,j,k}+dp_{i-1,j-1,k-p_i}\)。可以 \(70\) 分。
正解好神。首先发现每个东西的贡献是 \(E(\min(T))\) 乘上一堆系数。那么我们直接 dp 这一堆系数是什么东西。
设 \(dp_{i,j,k}\) 是前 \(i\) 个物品， \(\sum_{i\in T}=j\)，\(k\) 为当前 \(k\) 的 \((-1)^{|T|-k}\binom{|T|-1}{k-1}\) 之和。每次考虑选不选当前的物品，有：
- 不选：\(dp_{i-1,j,k}\)。
- 选：选了之后 \(|T|\) 增加，变成 \((-1)^{|T|-k+1}\binom{|T|}{k-1}\)。拆一下：
成了。关于初值，\(\binom{-1}{-1}=0\)，所以直接 \(dp_{0,0,0}=1\) 即可。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define int long long
using namespace std;
const int mod=998244353;
int n,m,K,ans,dp[2][10010][12],p[1010];
int qpow(int a,int b){
int ans=1;
while(b){
if(b&1)ans=1ll*ans*a%mod;
a=1ll*a*a%mod;
b>>=1;
}
return ans;
}
signed main(){
scanf("%lld%lld%lld",&n,&K,&m);K=n-K+1;
for(int i=1;i<=n;i++)scanf("%lld",&p[i]);
dp[0][0][0]=1;
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
for(int k=0;k<=K;k++){
dp[i&1][j][k]=dp[(i&1)^1][j][k];
if(j>=p[i]&&k)dp[i&1][j][k]=(dp[i&1][j][k]+dp[(i&1)^1][j-p[i]][k-1]-dp[(i&1)^1][j-p[i]][k]+mod)%mod;
}
}
}
for(int i=1;i<=m;i++){
ans=(ans+1ll*dp[n&1][i][K]*qpow(i,mod-2)%mod*m)%mod;
}
printf("%lld\n",ans);
return 0;
}