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;
- }
[bzoj4872] [洛谷 P3750] [六省联考 2017] 分手是祝愿
来源: http://www.bubuko.com/infodetail-3108571.html