您现在的位置是:首页 > 正文

2019 Multi-University Training Contest 7-1011 Kejin Player

2024-01-30 21:05:26阅读 0

题面链接:Kejin Player
求个期望;

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<utility>
#define scan(x) scanf("%d",&x)
#define print(x) printf("%d",x)
#define reset(x,y,n) memset(x,y,sizeof(int)*(n+1))
#define inc(i,x,n) for(register int i=x;i<=n;++i)
#define dec(i,x,n) for(register int i=x;i>=n;--i)
#define lson o<<1,l,M
#define rson o<<1|1,M+1,r
#define lo o<<1
#define ro o<<1|1
using namespace std;
const int N=1e6+5;
const int Mod=1e9+7;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
inline int read();
inline void write(int x);
long long dp[N];
ll quickpow(ll a, ll b)
{
    ll tmp = 1;
    while(b)
    {
        if(b&1)
            tmp = tmp*a%Mod;
        a = a*a%Mod;
        b >>= 1;
    }
    return tmp;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,Q;
        scanf("%d%d",&n,&Q);
        dp[1]=0;
        inc(i,2,n+1){
            long long r,s,x,a;
            scanf("%lld%lld%lld%lld",&r,&s,&x,&a);
            if(r==s)
            {
                dp[i]=(a+dp[i-1])%Mod;
                continue;
            }
            dp[i] = (s*a%Mod+(s-r)*(dp[i-1]-dp[x]+Mod)%Mod)%Mod*quickpow(r,Mod-2)%Mod;
            dp[i] += dp[i-1];
            dp[i] %= Mod;
        }
        while(Q--)
        {
            int  l, r;
            scanf("%d %d",&l,&r);
            printf("%lld\n",(dp[r]-dp[l]+Mod)%Mod);
        }
    }
    return 0;
}
inline int read(){
    int x=0,symbol=1;char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') symbol=-1;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    return x*symbol;
}
inline void write(int x){
    if(x>=10)write(x/10);
    putchar(x%10+'0');
}

网站文章