[HEOI2017]分手是祝愿 期望概率dp 差分

经分析可知：I.操作每个灯可看做一种异或状态 II.每个状态可看做是一些异或状态的异或和，而且每个异或状态只能由它本身释放或放入 III.每一种异或状态只有存在不存在两中可行状态，因此这些灯只有同时处于不存在才可以，而两种异或状态之间没有关系因此可以把这些状态看做一样的，因此counts的是异或状态数。

到这里为止我们可以得到一个简单的转移方程 f[i]=i/n*f[i-1]+(n-i)/i*f[i+1]+1 于是看起来似乎已经到了解决问题的时候，所以我就开始推…….然后就没有然后了，由这个式子出发的扔锅，永远没头…..

.最后知道正解是差分的我大概……我们可以这样想，从每个f[i]出发到达最后他一定是先从自己出发再到每个可能第一次到达i-1，在每个可能第一次到达i-2….而我们发现对于一个i到达i-1的期望次数是一定的因此我们可以从此入手 得到 g[i]=i/n+(n-i)/n(g[i+1]+g[i]+1) 这样我们就能用一个二阶递推来AC了

(*@ο@*) 哇～ 神™差分，让我推一年我也推不出来…….

#include<cstdio>
#include<iostream>
#define MAXN 100100
using namespace std;
typedef long long LL;
const LL P=;
LL jie[MAXN],g[MAXN],f[MAXN],n,k;
int now[MAXN];
inline LL ni(LL x)
{
   LL y=P-,ans=;;
   while(y)
   {
     if(y&)ans=ans*x%P;
     y>>=;
     x=x*x%P;
   }
   return ans;
}
int main()
{
    scanf("%lld%lld",&n,&k);
    jie[]=;
    for(LL i=;i<=n;i++)
     jie[i]=jie[i-]*i%P;
    for(LL i=;i<=k;i++)
     g[i]=jie[n];
    g[]=;
    g[n]=jie[n];
    for(LL i=n-;i>k;i--)
     g[i]=((n-i)*g[i+]%P+n*jie[n]%P)%P*ni(i)%P;
    for(int i=;i<=n;i++)
     scanf("%d",&now[i]);
    LL aim=;
    for(int i=n;i>;i--)
    if(now[i])
    {
      aim++;
      int j=;
      for(;j*j<i;j++)
       if(i%j==)
        now[j]^=,now[i/j]^=;
      if(j*j==i)
       now[j]^=;
    }
    LL ans=;
    for(int i=;i<=aim;i++)
     ans+=g[i];
    ans%=P;
    printf("%lld",ans);
    return ;
}