六省联考2017 分手是祝愿

· · 题解

略有订正，求管理员通过。

不知道什么时候过的题，今天看到有同学在做，觉得有必要写一写题解。

题目

题意：有一个长度为 n 的 01 串，下标编号 1 到 n。对位置 p 操作一次可以使所有编号为 p 的约数的位置 0 变 1，1 变 0。目标是使所有位置变成 0。B 君先随机操作若干次，等到当前局面可以在 k 次操作以内达成目标时就使用最优策略，达成目标后结束操作。求期望操作次数。

容易证明，一种最优的操作策略是每次操作最右边的为 1 的位置，直到达成目标。而且操作的先后顺序并不重要。

设 f_i 表示当前最优策略需要 i 步，从当前局面达到目标的期望步数。

则

f_i= \begin{cases} i(i\le k)\\ \frac{i}{n}f_{i-1}+\frac{n-i}{n}f_{i+1}+1(i > k) \end{cases}

暴力高斯消元复杂度爆炸。

设 f_i=f_{i-1}+b_{i}，那么我们发现 b_i是好求的。

f_i=\frac{i}{n}f_{i-1}+\frac{n-i}{n}f_{i+1}+1

代入得 f_i=\frac{i}{n}(f_i-b_i)+\frac{n-i}{n}(f_{i}+b_{i+1})+1

整理得到 b_i=\frac{(n-i)b_{i+1}+n}{i}

边界条件 b_n=1

做完了。

以下代码时间复杂度为 O(n^{1.5})。如果使用一些数论技巧来优化，可以做到 O(n\log n)。

#include<cstdio>
const int N=1e5+1,M=1e5+3;
int n,m,c,a[N],inv[M],f[N],b[N];
inline int F(int n){return n?1ll*F(n-1)*n%M:1;}
int main(){
    int t;
    inv[1]=1;
    for(int i=2;i<M;i++)inv[i]=1ll*inv[M%i]*(M-M/i)%M;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",a+i);
    for(int i=n,j;i;i--)if(a[i]){
      for(j=1;j*j<i;j++)
        if(i%j==0)a[j]^=1,a[i/j]^=1;
      if(j*j==i)a[j]^=1;
      c++;
    }
    if(m==n||m==n-1)return 0*printf("%lld",1ll*F(n)*c%M);
    for(int i=0;i<=m;i++)f[i]=i;
    b[n]=1;
    for(int i=n-1;i>m;i--)
      b[i]=(1ll*(n-i)*b[i+1]+n)%M*inv[i]%M;
    for(int i=m+1;i<=n;i++)f[i]=(f[i-1]+b[i])%M;
    return 0*printf("%lld",1ll*F(n)*f[c]%M);
}