概率期望DP做题记录-Part3
P3750 [六省联考 2017] 分手是祝愿
什么题目名称
题意
给定 \(n\) 个灯的初始状态，每个灯有两个状态亮和灭，通过操作第 \(i\) 个开关，所有编号为 \(i\) 的约数（包括 \(1\) 和 \(i\)）的灯的状态都会被改变，即从亮变成灭，或者是从灭变成亮。
你的目标是使所有灯都灭掉。
每次你会等概率随机操作一个开关，直到所有灯都灭掉。
B 君想知道按照这个策略（也就是先随机操作，最后最小操作次数小于等于 \(k\) 步时，再使用操作次数最小的操作方法）的操作次数的期望。
求这个期望乘以 \(n\) 的阶乘对 \(100003\) 取模之后的结果。\(n\le 10^5\)。
做法
先考虑已知这些路灯的亮灭状态，如何求出最小操作次数。
不难发现，从 \(n\) 到 \(1\)，有亮的就把它按掉，一定是最优的。
不妨假设当前位置为 \(i\)。
- 当 \(i=n\) 时，只能把 \(i\) 按灭掉。
- 当 \(1\le i\le n\) 时，假设 \([i+1,n]\) 都灭了。首先，更小的不能让 \(i\) 灭掉。如果试图用更大的把 \(i\) 按掉，那么就会一直需要更大的把按亮的按回去，直到没有更大的能把它按回去，这时候还是要一个一个按回去，不如直接把 \(i\) 按掉。
这样感性理解，就说明了从大到小按掉是最优的做法之一。
对于一个序列，根据刚才的过程，容易发现，需要按一下的点是固定的。因为这个操作是异或，所以顺序没有影响。
现在问题就转化成了，给定一个 \(01\) 串，每次随机选定一个位置异或 \(1\)，问变成全 \(0\) 的期望步数。
然后就好做了。容易发现期望步数只与 \(1\) 的个数有关，而且最小操作次数等于 \(1\) 的数量。
不妨设 \(dp_i\) 表示从有 \(i\) 个 \(1\) 变成 \(i-1\) 个 \(1\) 的期望步数。
显然转移为：
\[\begin{align} dp_i&=\frac{i}{n}+\frac{n-i}{n}(dp_i+dp_{i+1}+1)\nonumber\\ dp_i&=\frac{i}{n}+\frac{n-i}{n}dp_i+\frac{n-i}{n}dp_{i+1}+\frac{n-i}{n}\nonumber\\ dp_i&=1+\frac{n-i}{n}dp_i+\frac{n-i}{n}dp_{i+1}\nonumber\\ dp_i-\frac{n-i}{n}dp_i&=1+\frac{n-i}{n}dp_{i+1}\nonumber\\ \frac{i}{n}dp_i&=1+\frac{n-i}{n}dp_{i+1}\nonumber\\ dp_i&=1+\frac{n+(n-i)dp_{i+1}}{i}\nonumber\\ \end{align} \]直接转移即可。
那么步数的期望就是 \(E=\sum_{i=k+1}^{count}dp_i+k\)。\(count\) 表示初始 \(1\) 的数量。
直接计算即可，记得要乘上 \(n!\)。
代码
void update(int x){
for(int i=1;i*i<=x;i++){
if(x%i)continue;
a[i]^=1;
if(i*i!=x)a[x/i]^=1;
}
}
signed main(){
n=read(),m=read();
for(int i=1;i<=n;i++)a[i]=read();
for(int i=n;i;i--){
if(a[i]){
update(i);
++cnt;
}
}
m=min(cnt,m);
for(int i=n;i;i--)dp[i]=(n+(n-i)*dp[i+1])%mod*inv(i)%mod;
for(int i=m+1;i<=cnt;i++)ans=(ans+dp[i])%mod;
ans+=m;
for(int i=1;i<=n;i++)ans=ans*i%mod;
cout<<ans;
return 0;
}