BZOJ 4827 [Shoi2017]分手是祝愿 ——期望DP

显然，考虑当前状态最少需要几步，直接贪心即可。

显然我们只需要考虑消掉这几个就好了。

然后发现，关系式找出来很简单，是$f(i) f(i+1) f(i-1)$之间的。

但是计算的时候并不好算。

所以把意义进行差分用$g(i)$表示从$i$到$i-1$期望的次数。

然后就找到了二阶递推式递推即可。

#include <map>

#include <ctime>

#include <cmath>

#include <queue>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define F(i,j,k) for (int i=j;i<=k;++i)

#define D(i,j,k) for (int i=j;i>=k;--i)

#define md 100003

#define ll long long

#define maxn 100005

int n,k,a[maxn],g[maxn],cnt,fac,inv[maxn];

int main()

{

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

    fac=1;F(i,2,n)fac=(ll)fac*i%md;

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

    D(i,n,1)

    {

        if (a[i])

        {

            ++cnt;

            F(j,1,sqrt(i))

                if (i%j==0)

                {

                    a[i/j]^=1;

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

                }

        }

    }

    if (cnt<=k) {printf("%d\n",(ll)cnt*fac%md);return 0;}

    F(i,1,k) g[i]=1; g[n]=1;

    inv[1]=1;F(i,2,n) inv[i]=(ll)(md-md/i)*inv[md%i]%md;

    D(i,n-1,k+1) g[i]=((ll)(n-i)*g[i+1]%md+n)*inv[i]%md;

    int ans=0;

    F(i,1,cnt) ans+=g[i],ans%=md;

    printf("%d\n",(ll)ans*fac%md);

}