题目描述

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

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

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

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

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

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

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

$Solution:$

好神啊。

首先考虑怎么做才是最优策略，不难得出一个猜想：从右向左操作，能关就关。

感性理解一下，编号小的肯定无法控制编号大的，而每个编号进行操作所影响的集合也是一定的(与它目前的状态无关)。既然编号大的且亮着的迟早都要按，而且影响也是确定的，那不如先按它确定了状态来进行接下来的处理。

另外，这样显然每个灯最多操作一次，所以最优步数一定不大于n。

对于每个状态，最优策略是唯一确定的，那么我们就可以用最优策略下的操作数来代表每个状态。

如果在$i$状态进行正确的操作，$i$就会变成$i-1$。反之，如果操作不正确，它就会变成$i+1$。

对随机的部分，设$dp[i]$为从$i$到$i-1$所需的期望步数。

根据之前的推论，不难得到：$dp[i]=1 \times \frac{i}{n} + \frac{n-i}{n} \times (dp[i]+dp[i+1]+1)$

按对了一步跳过去，按错了回到$i+1$，还需要$dp[i+1]+dp[i]+1$才能跳到$i-1$。

化简得到$dp[i]=\frac{(n-i)dp[i+1]+n}{i}$，先求个$\sum$，再和采取最优策略部分的步数拼一下就是答案。

#include<cstdio>

#include<iostream>

#include<cstring>

#include<vector>

using namespace std;

const int N=1e5+5;

typedef long long ll;

const ll mod=1e5+3;

int n,K,a[N];

vector<int> fact[N];

ll fac=1,ans,dp[N];

ll qpow(ll x,ll y)

{

    ll res=1;x=x%mod;

    while(y)

    {

        if(y&1)res=res*x%mod;

        x=x*x%mod;

        y>>=1;

    }

    return res;

}

void ini()

{

    for(int x=1;x<=n;x++)

    {

        fac*=1LL*x,fac%=mod;

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

        {

            if(x%i)continue;

            if(i*i==x)fact[x].push_back(i);

            else fact[x].push_back(i),fact[x].push_back(x/i);

        }

    }

}

int main()

{

    scanf("%d%d",&n,&K);

    ini();

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

        scanf("%d",&a[i]);

    int step=0;

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

    {

        if(!a[i])continue;

        step++;

        for(int j=0;j<fact[i].size();j++)

            a[fact[i][j]]^=1;

    }

    if(step<=K)

    {

        printf("%lld\n",1LL*step*fac%mod);

        return 0;

    }

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

    {

        ll inv=qpow(i,mod-2);

        dp[i]=(1LL*(n-i)*dp[i+1]%mod+n%mod)%mod;

        (dp[i]*=inv)%=mod;

    }

    for(int i=K+1;i<=step;i++)

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

    (ans+=K)%=mod;

    (ans*=fac)%=mod;

    cout<<ans<<endl;

    return 0;

}

巴特西

[六省联考2017]分手是祝愿题解(期望dp)

$Solution:$

最新文章

热门文章

巴特西

[六省联考2017]分手是祝愿 题解(期望dp)

$Solution:$

最新文章

热门文章

[六省联考2017]分手是祝愿题解(期望dp)