浙农大第十九届程序设计竞赛 A-锯锯锯锯锯锯锯锯锯锯锯锯锯锯

锯锯锯锯锯锯锯锯锯锯锯锯锯锯

分析

牛客评测机挺快。这道题，千万不要无脑开1e8的数组(比如我)，把所有的询问离线下来，以次数为关键字排一个序，然后就按顺序扫着走，记录答案即可

代码

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int N=1e5+10;
const int mod=1e9+7;

ll n,tot;
ll ans[N],cnt[N];

struct nkl
{
    ll x,id;
}s[N<<2];

inline void add(ll i,ll x)
{
    s[++tot].id=i;
    s[tot].x=x;
}

inline bool god(nkl xx,nkl yy)
{
    return xx.x<yy.x;
}

inline ll get(ll x,ll y)
{
    ll ret=1;
    for (;y;y>>=1,x=x*x%mod)
        if(y&1) ret=ret*x%mod;

    return ret;
}

int main()
{
    scanf("%lld",&n);
    for (ll i=1;i<=n;i++)
    {
        ll x,y;
        scanf("%lld%lld",&x,&y);
        add(i,x);add(i,y);
    }sort(s+1,s+tot+1,god);

    ll now=1,st=0;
    for (ll i=1;i<=tot;i++)
    {
        while(st<s[i].x)
            ++st,now=(now*now+now)%mod;
        if(!ans[s[i].id]) ans[s[i].id]=now;
        else ans[s[i].id]=now*get(ans[s[i].id],mod-2)%mod;
    }

    for (ll i=1;i<=n;i++) printf("%lld\n",ans[i]);

    return 0;
}