BZOJ 4872 分手是祝愿

策略就是贪心，每次选最大的没被翻转的。

dp[i]表示在该策略下从还有i步达到最优到还有i-1步达到最优的期望步数，然后转移。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#define mod 100003
#define maxn 100050
using namespace std;
long long n,a[maxn],cnt=0,dp[maxn],k,ans=0;
long long f_pow(long long a,long long b)
{
    long long ans=1,base=a;
    while (b)
    {
        if (b&1) ans=(ans*base)%mod;
        base=(base*base)%mod;
        b>>=1;
    }
    return ans;
}
long long inv(long long x) {return f_pow(x,mod-2);}
int main()
{
    scanf("%lld%lld",&n,&k);
    for (long long i=1;i<=n;i++) scanf("%lld",&a[i]);
    for (long long i=n;i>=1;i--)
    {
        if (!a[i]) continue;cnt++;
        for (long long j=1;j*j<=i;j++)
        {
            if (i%j) continue;
            a[j]^=1;
            if (j*j!=i) a[i/j]^=1;
        }
    }
    for (long long i=n;i>=1;i--)
        dp[i]=((n-i)*dp[i+1]%mod+n)%mod*inv(i)%mod;
    if (cnt<k || n==k) ans=cnt;
    else
    {
        for (long long i=cnt;i>k;i--) ans=(ans+dp[i])%mod;
        ans=(ans+k)%mod;
    }
    for (long long i=1;i<=n;i++) ans=(ans*i)%mod;
    printf("%lld
",ans);
    return 0;
}