[bzoj4872] [洛谷P3750] [六省联考2017] 分手是祝愿

拼搏现实的明天。 2021-11-11 01:12 258阅读 0赞

### Description ###

> Zeit und Raum trennen dich und mich.  
> 时空将你我分开。

\$B\$ 君在玩一个游戏，这个游戏由 \$n\$ 个灯和 \$n\$ 个开关组成，给定这 \$n\$ 个灯的初始状态，下标为  
从 1 到 \$n\$ 的正整数。每个灯有两个状态亮和灭，我们用 1 来表示这个灯是亮的，用 0 表示这个灯是灭的，游戏  
的目标是使所有灯都灭掉。但是当操作第 \$i\$ 个开关时，所有编号为 \$i\$ 的约数（包括 1 和 \$i\$）的灯的状态都会被  
改变，即从亮变成灭，或者是从灭变成亮。\$B\$ 君发现这个游戏很难，于是想到了这样的一个策略，每次等概率随机  
操作一个开关，直到所有灯都灭掉。这个策略需要的操作次数很多， \$B\$ 君想到这样的一个优化。如果当前局面，  
可以通过操作小于等于 \$k\$ 个开关使所有灯都灭掉，那么他将不再随机，直接选择操作次数最小的操作方法（这个  
策略显然小于等于 \$k\$ 步）操作这些开关。\$B\$ 君想知道按照这个策略（也就是先随机操作，最后小于等于 \$k\$ 步，使  
用操作次数最小的操作方法）的操作次数的期望。这个期望可能很大，但是 \$B\$ 君发现这个期望乘以 \$n\$ 的阶乘一定  
是整数，所以他只需要知道这个整数对 100003 取模之后的结果。

### Input ###

第一行两个整数 \$n, k\$。  
接下来一行 \$n\$ 个整数，每个整数是 0 或者 1，其中第 \$i\$ 个整数表示第 \$i\$ 个灯的初始情况。  
\$1 \\leq n \\leq 100000, 0 \\leq k \\leq n\$；

### Output ###

输出一行，为操作次数的期望乘以 \$n\$ 的阶乘对 100003 取模之后的结果。

### Sample Input ###

4 0

0 0 1 1

### Sample Output ###

512

--------------------

## 想法 ##

又是个小文艺题，原谅我有点激动。。。

首先从 \$n\$ 到 \$1\$ 扫一遍，哪些灯需要被按1次是可以知道的，而且必须按这些灯。  
如果不小心按了其他的灯，就必须再按一次变回来。

神奇的 \$dp\$ 方式，设 \$f\[i\]\$ 表示从最少需要按 \$i\$ 次的状态变到最少需要按 \$i-1\$ 次的状态的期望步数。

随机按一次，按中 \$i\$ 个需要按的键之一的概率是 \$\\frac\{i\}\{n\}\$ ，按后变到了至少按 \$i-1\$ 次的状态，步数为1

若没有按中需要的键，概率是 \$\\frac\{n-i\}\{n\}\$ ， 此时至少需要按 \$i+1\$ 个键，应再按 \$f\[i+1\]\$ 次恢复至少按 \$i\$ 次的状态，再按 \$f\[i\]\$ 次到至少 \$i-1\$ 次的状态，总共步数为 \$1+f\[i+1\]+f\[i\]\$

综上所述，可列出式子  
$  
f\[i\]=\\frac\{i\}\{n\}+\\frac\{n-i\}\{n\}(1+f\[i+1\]+f\[i\])  
$  
合并同类项，整理一下得出  
$  
f\[i\]=\\frac\{n+(n-i)f\[i+1\]\}\{i\}  
$  
边界条件 \$f\[n\]=1\$

从 \$n\$ 往前求 \$f\[\]\$ ，一直求到 \$f\[k+1\]\$  
扫一遍得出原状态至少按的次数 \$t\$  
若 \$t \\leq k\$ ，则总期望值就是 \$t\$ ； 否则是 \$k+\\sum\\limits\_\{i=k+1\}^t f\[i\]\$

最后别忘了乘以 \$n\$ 的阶乘！

--------------------

## 代码 ##

#include<cstdio> #include<iostream> #include<algorithm> #define xzy 100003 using namespace std; const int N = 100005; typedef long long ll; int n,k,t; int a[N]; int Pow_mod(int x,int y){ int ret=1; while(y){ if(y&1) ret=((ll)ret*x)%xzy; x=((ll)x*x)%xzy; y>>=1; } return ret; } int f[N],inv[N]; int main() { scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) scanf("%d",&a[i]); t=0; for(int i=n;i>0;i--){ if(!a[i]) continue; t++; for(int j=1;j*j<=i;j++) if(i%j==0){ a[j]^=1; if(j*j!=i) a[i/j]^=1; } } inv[1]=1; for(int i=2;i<=n;i++) inv[i]=xzy-1ll*(xzy/i)*inv[xzy%i]%xzy; int ans=k; f[n]=1; for(int i=n-1;i>k;i--) f[i]=(1ll*(n-i)*f[i+1]%xzy+n)%xzy*inv[i]%xzy; if(t<=k) ans=t; else for(int i=k+1;i<=t;i++) ans=(ans+f[i])%xzy; for(int i=2;i<=n;i++) ans=((ll)ans*i)%xzy; printf("%d\n",ans); return 0; }

转载于:https://www.cnblogs.com/lindalee/p/11108315.html