Lottery

题目:是给你n个ai,一个xi,代表有xi个2^ai,然后问你拿这些最多可以组成多少个不同的数.xi和ai的范围都是1e9级别的,n是1e5级别的.
首先对于每个ai和xi来说,我们考虑它能延申到的长度.假如没有交集很显然就是直接乘起来就好了.假如有交集也挺显然的,就是拿前面能扩展到这里的最低位ai,拿2^(aj-ai)*xj即可,一个一个考虑计数就不会出现重复的现象.然后这题就没了.
代码如下:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int N=1e5+5;
struct JS{
    ll a,x,y;
}w[N<<2];

ll qp(ll a,ll b)
{
    ll res=1;
    while(b)
    {
        if(b&1) res=res*a%mod;
        b>>=1;
        a=a*a%mod;
    }return res;
}

bool cmp(JS l,JS r)
{
    if(l.a==r.a)    return l.x<r.x;
    else            return l.a<r.a;
}

int main()
{
    int T,g=0;
    scanf("%d",&T);
    while(T--)
    {
        ll n;
        scanf("%lld",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%lld%lld",&w[i].a,&w[i].x);
            w[i].y=w[i].x;
        }sort(w+1,w+1+n,cmp);
        ll ans=1;
        for(int i=1;i<=n;)
        {
            int r=i;
            while(w[r+1].a-w[r].a<33&&r<n)
            {
                if((w[r].x)>>(w[r+1].a-w[r].a)==0)    break;
                w[r+1].x+=(w[r].x)>>(w[r+1].a-w[r].a);
                r++;
            }
            for(int j=i+1;j<=r;j++)
            {
                w[i].y=(w[i].y+qp(2,w[j].a-w[i].a)*w[j].y)%mod;
            }ans=ans*(w[i].y+1);
            i=r+1;
        }
        printf("Case #%d: %lld\n",++g,ans);
    }
    return 0;
}