P5510 水晶

2019/12/27 修改最后一个点的数据范围 Steve带领军队到达了黑暗势力的据点 然而，他发现黑暗势力正在使用水晶保护自己 为了突破防御，Steve开始用武器攻击水晶

黑暗势力的水晶已经排成了一排，而且数量很多 水晶可分为$n$组，第$i$组内有$a_i$个水晶，并且防御力均为$na_i$ Steve的武器也已经排成了一排，而且数量也很多 武器也可分为$n$组，第$i$组内有$b_i$个武器，并且攻击力均为$nb_i$ 每一轮攻击中，黑暗势力会选择一个水晶，Steve会选择一个武器 如果这个武器的攻击力大于水晶的防御力，这次攻击就有效 然而，水晶和武器数量太多了，Steve很难知道具体选择了哪个水晶，哪个武器 现在Steve希望知道： 1.对于所有可能的情况，有多少种选法是一次有效的攻击 2.如果已经知道选用水晶的防御力在第$x$组水晶的防御力和第$y$组水晶的防御力之间，且选用武器的攻击力在第$z$组武器的攻击力和第$u$组武器的攻击力之间，那么，有多少种选法是一次有效的攻击 也就是，选择的水晶防御力不小于第$x$组水晶和第$y$组水晶防御力的较小值，不大于两者的较大值，武器同理 两个选法不同，当且仅当选用的水晶或武器不同（可以在同一组） 由于战事紧迫，你需要迅速回答问题才能让Steve作出下一轮攻击的决策 因此，部分测试点强制在线 为了避免答案过大，答案对$998244353$取模

由于输入输出规模较大，使用下面的模板完成数据生成，具体格式请看模板和样例 评测时，所有测试点都只会输入5个数，输出1个数，因此你不需要输入输出优化 为便于调试，该模板可以手动指定数据，并输出每一个询问的答案，只需要输入的$k=0$ 对于所有测试点，保证调用交互库消耗的时间不超过300ms ``` #include using namespace std; #define u32 unsigned int #define u64 unsigned long long int cl; const int N=2500007; const long long M=998244353LL; int n,q,k; int a[N],na[N],b[N],nb[N]; int x,y,z,u; namespace lib{ u64 read(){ u64 n=0; char c=getchar(); while(c'9')c=getchar(); while(c>='0'&&c>8)%(r-l+1)+l); } int ra,t; void init(){ n=read();k=read(); if(k8)%(M-1)+1); //na[i]=rand(1,M-1); } s=bacs; for(int i=1;i>8)%ra+1); //a[i]=rand(1,ra); s=s*19260817+1; na[i]=((s>>8)%(M-1)+1); //na[i]=rand(1,M-1); } bacs=s; for(int i=1;i>8)%ra+1); //a[i]=rand(1,ra); s=s*19260817+1; //nb[i]=((s>>8)%(M-1)+1); } s=bacs; for(int i=1;i>8)%ra+1); //a[i]=rand(1,ra); s=s*19260817+1; nb[i]=((s>>8)%(M-1)+1); } } q=read(); } u64 lastans; u64 res; void reply(u64 num){ if(k8)%n+1); s=s*19260817+1; y=((s>>8)%n+1); s=s*19260817+1; z=((s>>8)%n+1); s=s*19260817+1; u=((s>>8)%n+1); //x=rand(1,n);y=rand(1,n);z=rand(1,n);u=rand(1,n); } if(k&1){ int t=lastans%n+1; if((x+=t)>n)x-=n; if((y+=t)>n)y-=n; if((z+=t)>n)z-=n; if((u+=t)>n)u-=n; /*x=(x+lastans)%n+1; y=(y+lastans)%n+1; z=(z+lastans)%n+1; u=(u+lastans)%n+1;*/ } } void stop(){ if(k>=2){write(res);putchar('\n');} } } int main(){ lib::init(); //现在你可以使用生成的a,na,b,nb //回答第一问 lib::reply(233); for(int i=1;i

如果$k=0$，则会分别输出每一问的答案 否则，只会输出一个整数用于检查结果是否正确

样例1解释： 当选择第二组武器时，一定能进行一次有效攻击 当选择第一组武器时，只有选择第一组水晶才能进行一次有效攻击 因而，不难求出每一问的答案 建议根据样例进一步理解题意 样例5与样例6一致 数据范围： 对于所有数据，满足$1\le x,y,z,u \le n$，$1\le a_i,b_i\le 10^9$，$1\le na_i,nb_i\le 998244352$ 如未特别说明，$k=3$，即：由模板生成数据，强制在线 如果$k=2$，那么这组数据仍由生成器生成，但不强制在线，也就是你可以在不回答询问的情况下得到下一个询问的真实值，随后按顺序回答即可 测试点| 分值| n | q| 特殊性质 :-: | :-: | :-: | :-: | :-: 1| 4| 100| 100| $k=2$| 2| 14| 3000| 3000| $k=2$| 3| 11| 100000| 100000| $a_i,b_i\le 100$| 4| 10| 15| 4000000| | 5| 12| 100| 4000000| | 6| 14| 5000| 4000000| | 7| 16| 100000| 100000| | 8| 19| 2500000| 4000000| |