分手是祝愿

有??盏灯，给定每一盏灯的初始状态。每次操作可以选择一盏灯，将它的所有因数和它翻转。每次操作策略如下：

1. 如果可以通过小于等于??次操作把所有灯灭掉，那么直接按照最优策略进行。
2. 否则，从1到??中随机选择一盏灯进行操作。

求把所有灯灭掉的期望步数。

1 ≤ ?? ≤ 10⁵

题解

首先策略是唯一的。（为什么？每次考虑最大的元素，它只能通过操作自己灭掉）

所以我们可以得到一个01串，里面的每一个位置表示这个位置是否需要翻转。

然后所有的位置就等价了。

设??_??表示有??盏灯亮着的时候，灭掉其中一盏灯的期望步数。

在吴清月的PPT上第一次见到状态设成走一步的期望，最后求和的模式。

1. 则当?? > ??时，
   有\(f_i=\frac in+\frac{n-i}n(1+f_{i+1}+f_i)\) ，即\(f_i=\frac ni+\frac{n-i}i f_{i+1}\)。
2. 当?? ≤ ??时??_?? = 1。

所以可以??(??)递推。

CO int N=100000+10;
int sta[N];
int dp[N];

int main(){
    int n=read<int>(),k=read<int>(); 
    for(int i=1;i<=n;++i) read(sta[i]);
    for(int i=n;i>=1;--i)if(sta[i]){
        for(int j=1;j*j<=i;++j)if(i%j==0){
            if(j!=i) sta[j]^=1;
            if(i/j!=j and i/j!=i) sta[i/j]^=1;
        }
    }
    int tot=0;
    for(int i=1;i<=n;++i) tot+=sta[i];
    for(int i=1;i<=k;++i) dp[i]=1;
    dp[n]=1;
    for(int i=n-1;i>k;--i){
        int inv=fpow(i,mod-2);
        dp[i]=add(mul(n,inv),mul(n-i,mul(inv,dp[i+1])));
    }
    int ans=0;
    for(int i=tot;i>=1;--i) ans=add(ans,dp[i]);
    for(int i=1;i<=n;++i) ans=mul(ans,i);
    printf("%d\n",ans);
    return 0;
}

SHOI2017 分手是祝愿

原文：https://www.cnblogs.com/autoint/p/11750228.html