思维+二进制+递归分治

首先一个重要的策略
我们先对数据从小到大排序

然后如果一个前缀和,比后面的阶数要小
那么,我们此刻就可以将这个数组分开单独看

这里就是分治了

答案是两边结果的乘积

然后对于一个没有被分开的数组,我们该如何求解他的答案呢?
答案就是将他的每一阶数全都转化为当前区间的最小的那个阶数

统计这个数目即可!

#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int max_n = 1e5+100;
const ll mod = 1e9+7;
pii ans[max_n];

ll POW(ll base,ll p)
{
    ll ans = 1;
    while (p)
    {
        if (p&1)ans=ans*base%mod;
        base=base*base%mod;
        p>>=1;
    }
    return ans;
}

ll Solve(int lft,int rgt)
{
    ll po = ans[lft].first;
    ll sum = ans[lft].second;
    ll mp=po;
    ll cur=sum;
    for (int i=lft+1;i<=rgt;++i)
    {
        ll tmp = ans[i].second;
        ll p = ans[i].first;

        while (mp<p)
        {
            if (cur<2)break;
            cur>>=1;
            ++mp;
        }

        if (p>mp)
        {
            return ((sum+1)*Solve(i,rgt)%mod)%mod;
        }

        cur+=tmp;
        sum = (sum+tmp*POW(2,p-po)%mod)%mod;
    }
    return (sum+1)%mod;
}

int n;
int main()
{
    ios::sync_with_stdio(0);
    int T;cin>>T;
    for (int t=1;t<=T;++t)
    {
        map<int,int> mp;
        cin>>n;
        int cnt=0;
        for (int i=1,ai,xi;i<=n;++i)
        {
            cin>>ai>>xi;
            mp[ai]+=xi;
        }
        for (pii p:mp)
        {
            ans[++cnt]=p;
        }

        sort(ans+1,ans+1+cnt);

        cout<<"Case #"<<t<<": ";
        cout<<Solve(1,cnt)<<endl;
    }
}