HDU 6656 Kejin Player

Time limit 5000 ms
Memory limit 524288 kB
OS Windows

解题思路

因为升级只能一级一级地升，所以所求期望满足了区间加的性质，可以一级一级地算，然后求前缀和、输出（状态不好，临博客涕零，不知所言）

接着扔链接（留坑）

这篇博客推公式的时候好像有些地方下标有点错，而且推公式的过程省了不少（雾）https://blog.csdn.net/toohandsomeIeaseId/article/details/99357608
这篇推公式的方向对我来说好新颖，进行非整数次的氪金，这样就不用死磕无穷级数了……（我的猴子排序那篇也可以计算快点了）https://blog.csdn.net/qq_41785863/article/details/99347386

源代码

参考别人博客写的，感觉像抄的一样

#include<stdio.h>

const int mod=1e9+7;

const int MAXN=5e5+5;

int T;

int n,m;

long long inv(long long x)//快速幂求逆元 inv[a]=a^(p-2)

{

    long long res=1LL;

    long long b=mod-2;

    while(b){

        if(b&1) res=res*x%mod;

        x*=x;

        x%=mod;

        b>>=1;

    }

    return res%mod;

}

long long sum[MAXN];

int main()

{

    scanf("%d",&T);

    while(T--)

    {

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

        sum[0] = 0;

        for(int i = 1; i <= n; ++i)

        {

            long long r, s, x, a;

            scanf("%lld%lld%lld%lld", &r, &s, &x, &a);

            long long p =  r * inv(s) % mod;

            sum[i] = (sum[i - 1] + (a + (1 - p + mod) % mod * (a + sum[i - 1] - sum[x - 1] + mod) % mod * inv(p) % mod) % mod + mod) % mod;//关键就是这个了

        }

        while(m--)

        {

            int l, r;

            scanf("%d%d", &l, &r);

            long long ans = (sum[r - 1] - sum[l - 1] + mod) % mod;//这里为啥来着……

            printf("%lld\n", ans);

        }

    }

    return 0;

}

巴特西

HDU 6656 Kejin Player

解题思路

源代码

最新文章

热门文章