婚庆网站开发的意义,济南槐荫区做网站的,wordpress广告插件下载,物业网站建设方案Lottery Gym - 102822L
题意#xff1a;
有n个盒子#xff0c;每个盒子有x个球#xff0c;每个球的数值为2a,问最多能组成多少数#xff1f;答案mod 1e97
题解#xff1a;
二进制思维题#xff0c;浓浓的cf风格 参考题解 我们将数按照幂次进行排序#xff08;从小到…Lottery Gym - 102822L
题意
有n个盒子每个盒子有x个球每个球的数值为2a,问最多能组成多少数答案mod 1e97
题解
二进制思维题浓浓的cf风格 参考题解 我们将数按照幂次进行排序从小到大然后对于每一位i我们考虑下一位i1的位置是否可以用第i位表示出来 比如当前位是25下一位是41 当前位是有5个22,下一位是24,我们用4个22就可以表示出24说明第i1位可以被第i位表示。然后我们把第i位所能表示第i1位的数量加给原本第i1位的数量看第i1位是否能表示第i2位依次类推 如果可以被表示我们就把第i位和第i1位看作是一个连续的段然后我们求出所有的段把一个段内的所有指数a都化解成这个段内最小指数amin段内相加段与段之间乘积得到答案 例子 n3 (1,3),(2,3),(4,1) 我们发现他们是一个连续的段内这个段内最小的指数为1所有都化成这个指数。41可以化成(2,4),加上原先的(2,3)有2727又可以化成(1,14),原先就有(1,3)再加上题木允许什么也不选所以最后答案就是1 * 4 3 * 231 这是一个段的答案如果有多个段答案相乘(这个不选每一段都可以这样选) 为什么这样我也是看了其他人的题解才知道这个方法但是为什么这样做呢 如果第i个位可以表示出第i1个位说明第i个位和第i1个位之间的数均可以表示所以我们可以看作一段。我们将所有指数都化成该段最低位指数amin有x个amin而其能表示的数就是t * amin , t属于0~x所以答案是x1 段与段之间是独立的无法互相表示所以不同段的结果乘积 比如有(2,7)和(6,3)分别属于两个段 (2,7)所能表示的是4812…28 (6,3)所能表示的是: 64,128,192 两者可以彼此组合且不会重复如果会重复按照性质就会属于一个段
另 如果两个相邻的箱子的指数差距大于32的话那么他们是一定不会组成相同段的因为x最多1e9个能满足的a的差距就这么大了。
代码:
#includebits/stdc.h
using namespace std;
const int mod1e97;struct Node{long long a,x;
}a[100010];
long long b[100010];
bool cmp(Node a,Node b){return a.ab.a;
}
long long q_pow(long a,long b){long long res 1;a % mod;while(b){if(b 1) res res * a % mod;a a * a % mod;b 1 ;}return res;
}
int main(){int t;scanf(%d,t);for(int ti1;tit;ti){int n;scanf(%d,n);for(int i1;in;i)scanf(%lld%lld,a[i].a,a[i].x);sort(a1,an1,cmp);for(int i1;in;i)b[i]a[i].x;long long ans1;for(int l1,r;ln;lr1){rl;// a[r1].a-a[r].a表示指数差 (b[r](a[r1].a-a[r].a))为正说明第r位可以表示第r1位 while(r n (b[r](a[r1].a-a[r].a)) a[r1].a - a[r].a 32){//从l开始求所有组成的最长连续段 b[r1]b[r](a[r1].a-a[r].a); //将第r位所能表示的第r1位的数量加到原先第r1位的数量 r;}for(int ir;il;i--){//对段内的指数全部分解 a[i-1].x(a[i-1].xa[i].x*q_pow(2ll,a[i].a-a[i-1].a))%mod;}ansans*(a[l].x1)%mod;}// printf(%lld\n,ans);printf(Case #%d: %lld\n,ti,ans);}
}
