Fork me on GitHub

「SHOI2017」分手是祝愿 差分,期望dp

发表于 | 分类于
字数统计: 903字 | 阅读时长 ≈ 4分钟

Links there:LOJ-2145/SHOI2017

题意

B 君在玩一个游戏,这个游戏由 $N$ 个灯和 $N$个开关组成，给定这 $N$ 个灯的初始状态.下标为从 $1$ 到 $N$ 的正整数。

每个灯有两个状态亮和灭，我们用 $1$ 来表示这个灯是亮的，用 $0$ 表示这个灯是灭的，游戏的目标是使所有灯都灭掉。

但是当操作第 $i$ 个开关时，所有编号为 $i$ 的约数（包括 $1$ 和 $i$）的灯的状态都会被改变，即从亮变成灭，或者是从灭变成亮。

B 君发现这个游戏很难，于是想到了这样的一个策略，每次等概率随机操作一个开关，直到所有灯都灭掉。

这个策略需要的操作次数很多，B 君想到这样的一个优化。如果当前局面，可以通过操作小于等于 $k$ 个开关使所有灯都灭掉，那么他将不再随机，直接选择操作次数最小的操作方法（这个策略显然小于等于 $k$ 步）操作这些开关。

B 君想知道按照这个策略（也就是先随机操作，最后 小于等于 $k​$ 步，使用操作次数最小的操作方法）的操作次数的期望。

这个期望可能很大，但是 B 君发现这个期望乘以 $N$ 的阶乘一定是整数，所以他只需要知道这个整数对 $100003$ 取模之后的结果。

思路

bike的题就是简洁干净.

考虑$N=K$的情况,发现只要贪心从大到小取就行啦,所以50分是送的!?

令$f(i)$表示还有$i$步达成目标的期望步数.

但是这样并不好计算啊!在算$f(i)$的时候并不能保证都知道$f(i-1),f(i+1)$

考虑差分.差分$g$的意义就是从第$i$步到第$i-1$步的期望.

最终把$g(i)$加起来就是答案啦

CODE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
//my vegetable has exploded. :(
#include<bits/stdc++.h>
#define max(x,y) (x>y?x:y)
#define min(x,y) (x<y?x:y)
#define MM(x,y) memset(x,y,sizeof(x))
#define MCPY(a,b) memcpy(a,b,sizeof(b))
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,b,a) for(int i=b;i>=a;i--)
#define fi first
#define se second
#define int long long
using namespace std;

inline int quickpow(int m,int n,int p){int b=1;while(n){if(n&1)b=b*m%p;n=n>>1;m=m*m%p;}return b;}
inline int getinv(int x,int p){return quickpow(x,p-2,p);}
inline int read(void){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){f=ch=='-'?-1:1;ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	return x * f;
}
const int MAXN = 1e5+100;
const int Mod = 1e5+3;
int g[MAXN],n,k,lt[MAXN];
inline int calc(void){
    int ret = 0;
    for (int i = n; i; i--){
        if (lt[i]) {
            int tt = sqrt(i+0.5);
            ++ret;
            for (int j = 1; j <= tt; ++j) if(!(i%j)){
                lt[j] ^= 1;
                if (i != j * j) lt[i/j] ^= 1;
            }
        }
    }
    return ret;
}
///------------------head------------------
signed main(signed argc, char *argv[]){
    n=read(),k=read();
    int fac = 1,ans = 0;
    rep(i,1,n) fac = fac * i % Mod;
    rep(i,1,n) lt[i]=read();
    int t = calc();
    if (t <= k)
        return printf("%lld\n", t * fac % Mod),0;
    rep(i,1,k) g[i] = 1;
    g[n] = 1;
    per(i,n-1,k+1) g[i] = (1 + (g[i+1] + 1) * (n - i) % Mod * getinv(i,Mod) % Mod) % Mod;
    rep(i,1,t) {ans += g[i]; if (ans >= Mod) ans -= Mod;}
    ans = ans * fac % Mod;
    printf("%lld\n",ans);
	return 0;
}

/* Examples: */
/*
4 0
0 0 1 1
*/

/*
512
*/