wa到最后半小時才過，，，
對冪次排序
對于每一段可以連續進位進到的地方，從每一位乘以2的冪次轉移到最低位，那么這一段能夠得到的方案總數就是各位的數量在最低位上的總和
比如2^0有4個，2^1有1個，那么他最多就進位到2^2，不會影響2^3，所以直接把2^1上的1加到2^0上面，然后他們能得到所有不同的方案就是（6+1）=7,數字7是達不到的，后面如果2^3有1個，就直接乘以(1+1)，
即資料 3 \n 0 4 1 1 3 1 答案是(6+1)*(1+1)=14
注意判斷當前短累計和的時候，如果相鄰為冪次相差60以上直接不能繼續往右拓展，而不是(b[r]>>1000000)>0這樣判斷，不然會有問題(這里我也不太懂，有沒有好兄弟知道)，加了這個判斷就過了
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
struct Node{
long long a,x;
}a[100010];
long long b[100010];
bool cmp(Node a,Node b){
return a.a<b.a;
}
long long p(long long n){
long long x=2,ans=1;
for(;n;n>>=1,x=x*x%mod)if(n&1)ans=ans*x%mod;
return ans;
}
int main(){
int t;
//printf("%d",(1>>100000));
scanf("%d",&t);
for(int ti=1;ti<=t;ti++){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%lld%lld",&a[i].a,&a[i].x);
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++)b[i]=a[i].x;
long long ans=1;
for(int l=1,r;l<=n;l=r+1){
r=l;
if(r<n && (a[r+1].a-a[r].a)<=60)
{
while(r<n&&(b[r]>>(a[r+1].a-a[r].a))){
b[r+1]+=b[r]>>(a[r+1].a-a[r].a);
r++;
if(r<n && (a[r+1].a-a[r].a)>60)
break;
}
}
for(int i=r;i>l;i--){
a[i-1].x=(a[i-1].x+a[i].x*p(a[i].a-a[i-1].a))%mod;
}
ans=ans*(a[l].x+1)%mod;
}
printf("Case #%d: %lld\n",ti,ans);
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/201783.html
標籤：其他
下一篇：數字信號處理實驗一 T3