思维+二进制+递归分治
首先一个重要的策略
我们先对数据从小到大排序
然后如果一个前缀和,比后面的阶数要小
那么,我们此刻就可以将这个数组分开单独看
这里就是分治了
答案是两边结果的乘积
然后对于一个没有被分开的数组,我们该如何求解他的答案呢?
答案就是将他的每一阶数全都转化为当前区间的最小的那个阶数
统计这个数目即可!
#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; } }