[bzoj 4872][六省联考2017]分手是祝愿

传送门

Description

N个灯按照1~N标号，按下一个开关i，所有标号是i的约数的开关都改变状态，目标是关掉所有的灯，如果当前最优策略≤k就直接按照最优策略走。否则随机按下一个开关。给出每个灯的当前状态，问期望步数*n！（mod 100003）

Solution

•首先可以直接N个开关的最优策略需要的步数t，(最大的状态为开的灯一定要按，以此类推)

•状态i表示当前的数按照最优策略需要i步

•最后的状态看成是0

考虑f[i]表示从状态i到状态i-1的期望步数，最后答案是\(n!*\sum_{i=1}^{t} f[i] \ \ \mod 100003\)

当\(i \leq k\)或者\(i=n\)时，\(f[i]=1\)

\(f[i]=\frac{i}{n}+\frac{n-i}{n}(f[i+1]+f[i]+1) \ \ \ k<i<n\)

Code

#include<bits/stdc++.h>

#define ll long long

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

inline int read()

{

	int x=0,f=1;char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}

	return x*f;

}

#define MN 100005

#define mod 100003

int n,k,a[MN],t;

int mark[MN];

ll inv[MN],g[MN],fac;

int main()

{

    n=read();k=read();

    register int i,j;

    for(fac=i=1;i<=n;++i) a[i]=read(),fac=fac*i%mod;

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

	{

        int p=a[i];

        for(j=i<<1;j<=n;j+=i) if(mark[j]) p^=1;

        if(p) mark[i]=1,t++;

    }

    if(t<=k) return 0*printf("%lld",t*fac%mod);

    inv[1]=1;

    for(i=2;i<=n;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;

    for(i=1;i<=k;i++) g[i]=1;

    for(g[n]=1,i=n-1;i>k;--i) g[i]=((n-i)*g[i+1]%mod+n)*inv[i]%mod;

    ll ans=0;

    for(i=1;i<=t;++i) ans+=g[i];

    printf("%lld",ans*fac%mod);

    return 0;

}

Blog来自PaperCloud，未经允许，请勿转载，TKS！

巴特西

[bzoj 4872][六省联考2017]分手是祝愿

传送门

Description

Solution

Code

最新文章

热门文章