LOJ #2145. 「SHOI2017」分手是祝愿

题目链接

题解

一道画风正常的……期望DP？

首先考虑如何以最小步数熄灭所有灯：贪心地从大到小枚举灯，如果它亮着则修改它。可以求出总的最小步数，设为$cnt$。

然后开始期望DP。设$dp[i]$为当前最小步数是$i$，总最小步数是$i$，要达到最小步数是$i - 1$的状态，期望要走多少步。则有$\frac{i}{n}$的几率恰好走了该走的一步，而有$\frac{n - i}{n}$的几率走错了（回到了$dp[i + 1]$表示的状态）。

则：$$dp[i] = \frac{i}{n} + \frac{n - i}{n}(1 + dp[i + 1] + dp[i])$$

就可以推出来了。

答案就是：$(\sum_{i = k + 1}^{cnt} dp[i] + min(cnt, k)) * n!$

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <iostream>

#include <cstdlib>

#define space putchar(' ')

#define enter putchar('\n')

using namespace std;

typedef long long ll;

template <class T>

void read(T &x){

    char c;

    bool op = 0;

    while(c = getchar(), c < '0' || c > '9')

	if(c == '-') op = 1;

    x = c - '0';

    while(c = getchar(), c >= '0' && c <= '9')

	x = x * 10 + c - '0';

    if(op) x = -x;

}

template <class T>

void write(T x){

    if(x < 0) putchar('-'), x = -x;

    if(x >= 10) write(x / 10);

    putchar('0' + x % 10);

}

const int N = 100005, P = 100003;

int n, m, a[N], cnt;

ll dp[N], ans;

ll qpow(ll a, ll x){

    ll ret = 1;

    while(x){

	if(x & 1) ret = ret * a % P;

	a = a * a % P;

	x >>= 1;

    }

    return ret;

}

int main(){

    read(n), read(m);

    for(int i = 1; i <= n; i++) read(a[i]);

    for(int i = n; i; i--)

	if(a[i]){

	    cnt++;

	    for(int j = 1; j * j <= i; j++)

		if(i % j == 0){

		    a[j] ^= 1;

		    if(j * j < i) a[i / j] ^= 1;

		}

	}

    for(int i = n; i; i--)

	dp[i] = 1 + (n - i) * qpow(i, P - 2) % P * (1 + dp[i + 1]) % P;

    for(int i = cnt; i > m; i--)

	ans = (ans + dp[i]) % P;

    ans = (ans + min(cnt, m)) % P;

    for(int i = 2; i <= n; i++)

	ans = ans * i % P;

    write(ans), enter;

    return 0;

}

巴特西

LOJ #2145. 「SHOI2017」分手是祝愿

题目链接

题解

最新文章

热门文章