bzoj 4872[Shoi 2017]お別れはお祝い(期待確率DP)

bzoj 4872[Shoi 2017]お別れはお祝いです
原題住所:http://www.lydsy.com/JudgeOnline/problem.php?id=4872
題意:n個のランプとそれらの初期のスイッチング状態が与えられ、操作のたびにランプiが選択されると、すべてのiの約数が状態(iと1を含む)を変化させる.私たちは操作ですべての明かりを消します.ランプをランダムに選択するたびに、現在の最適ポリシー操作数≦kが最適ポリシーを直接使用する場合.希望操作数*n!%1000003の値.
データ範囲1≦n≦100000,0≦k≦n%50のデータはk=nを満たす.
标题:状態を表すDPしか思いつかなかったので、このような操作があるとは思わなかった...このk=nの一部のデータはヒントです:この場合、最善の方法は大きいものから小さいものまで、明るいものなら彼に操作することです.どうして?最大の点灯しているランプは、それ自体を操作しなければ、その倍数でしか操作できませんが、その倍数は多く押しても消されます.このように押すと、余分な操作が増えるだけで、最後にはこのランプ自体を押します.従って、1つのスイッチング状態に対して、その最適な態様は固定された唯一のものである.
そこで,我々の状態定義が生じた:f[i]は,最適スキームがi個のランプから最適スキームがi−1個のランプの所望の操作数であることを示す.このi個のランプは固定されているので、i/nの確率が合っていると、そのまま回転して、(n-i)/nの確率が間違ってf[i+1]を稼いだので、f[i]=in+n−in(1+f[i+1]+f[i])シフト:f[i]=(n+(n−i)∗f[i+1])iはf[n]=1を発見し、そのまま押すことができ、与えられた状態の本来の最適案がcntであれば、答えはk+Σcnti=kf[i]+1である
DPメンテナンスという差分値は一般的に考えにくいが、一般的な考え方dp[i]は、最適案がi個のランプからランプがないまでの所望の操作であることを示し、dp[i]=in∗dp[i−−1]+n−indp[i+1]+1というもの...初期化はf[k]=k、f[i]=f[i−[i−−1]+1であるが、シフトがより簡便なものを得ることができることを発見し、この差分群fを思いついた.
もとは型の任意の数かもしれないと推測して、だからやっとnに乗ります!ちょうど式の分母に対応しているので,逆元の問題を心配する必要はない.結果10003は質量数です.
コード:

#include
#include
#include
#include
using namespace std;
const int mod=100003;
const int N=100005;
int n,k,inv[N],a[N],ans=0;
int f[N],cnt=0;
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    inv[0]=1; inv[1]=1; 
    for(int i=2;i<=n;i++) inv[i]=1LL*(mod-(mod/i))*inv[mod%i]%mod;
    for(int i=n;i>=1;i--) if(a[i])
    {
        cnt++;
        for(int j=1;j*j<=i;j++) 
        if(i%j==0) { a[j]^=1; if(i/j!=j) a[i/j]^=1; }
    }
    if(cnt<=k) ans=cnt;
    else
    {
        f[n+1]=0; f[n]=1;
        for(int i=n-1;i>k;i--) f[i]=1LL*inv[i%mod]*((n+1LL*(n-i)*f[i+1]%mod)%mod)%mod;
        for(int i=cnt;i>k;i--) ans=(ans+f[i])%mod;
        ans=(ans+k)%mod;
    }
    for(int i=1;i<=n;i++) ans=(1LL*ans*i)%mod;
    printf("%d
",ans);
    return 0;
}