本文共 1551 字，大约阅读时间需要 5 分钟。

题意：

对题库有两种操作，一种是在ti时刻加一道题，一种是在ti时刻减一道题拿来比赛，问每道题待在题库里的期望时间。

思路：

从后往前考虑，当前项i为减一道题时，之前的题在这一时刻被取出的概率是1/k，k表示之前还剩多少道题，而在这之后取出的概率就是1-1/k，用sum表示从n到i+1之间某一刻取出的期望时间，那么从n到i某一刻取出的期望时间就是sum*（1-1/k）+1/k*time[i]。

代码：

#include 
   
    #define LL long longusing namespace std;const int maxn=1e5+5;const int mod=1e9+7;int a[maxn];int d[maxn];LL dp[maxn][32][3];int sum[32];LL cal(int n, int m){    if(m==0)return 0;    LL res=0;    d[1]=a[1];    memset(sum, 0, sizeof sum);    memset(dp, 0, sizeof dp);    for(int i=2; i<=n; i++)    {        int x=a[i]^a[i-1];//        printf("%d\n", x);        for(int j=0; j<=30; j++)        {            if((x>>j)&1)            {                dp[i][j][0]=dp[i-2][j][1];                dp[i][j][1]=dp[i-2][j][0]+1;            }            else             {                dp[i][j][0]=dp[i-2][j][0]+1;                dp[i][j][1]=dp[i-2][j][1];            }//            printf("%d ", dp[i][j][1]);        }//        printf("\n");        d[i]=d[i-1]^a[i];        if(i>=m+2)        {            int x=d[i]^d[i-m-2];            for(int j=0; j<=30; j++)            {                if((x>>j)&1)                {                    dp[i][j][1]--;                }                else dp[i][j][0]--;            }        }        for(int j=0; j<=30; j++)sum[j]+=dp[i][j][1];    }    for(int j=0;j<=30; j++)    {//        printf("%d ", sum[j]);        res=(res+(((1LL<
    
     >n>>l>>r;    for(i=1; i<=n; i++)    {        scanf("%d", &a[i]);    }    LL ans=cal(n, r/2*2)-cal(n, (l-1)/2*2);     ans=(ans%mod+mod)%mod;    cout<
     
      <
     
    
   

转载地址：http://wlywb.baihongyu.com/