1 乘
时间限制: 2s
空间限制: 256MB
1.1 题目描述
你有一个正整数 (a) , 有 (q) 次询问, 每次给定一个正整数 (b_i)
, 求 (a^{b_i}) 的值.
由于答案可能很大, 你只需要输出答案对 (p) 取模的结果。
又由于询问可能很多, 给定一个参数 (k), 你只需要输出对于所有 (k) 的整数倍 (i(0 < i ≤ q)) , 第一
次询问到第 (i) 次询问的结果的异或和.
为了防止输入文件过大, 每次询问的值以以下方法生成:
设 (b_i) 为第 (i) 次询问的值, 给定 (b_0, l, m, c,i > 0) 时,(b_i) 满足 (b_i = (m ∗ b_i−1 + c)mod l) 。
1.2 输入格式
第一行四个正整数 (a, p, q, k).
第二行四个正整数 (b_0, l, m, c).
1.3 输出格式
输出 (⌊frac{q}{k}⌋) 行, 第 i 行表示第一次到第 (i ∗ k) 次询问结果的异或和. 你不需要对异或和进行取模.
1.4 样例数据
1.4.1 样例 1 输入
4 3 9 6
5 8 7 7
1.4.2 样例 1 输出
0
1.4.3 样例 1 解释
b1 − b6 分别为 2, 5, 2, 5, 2, 5, 答案都是 1, 异或和为 0.
1.5 数据范围
对于前 10% 的数据, (q = 0);
对于前 50% 的数据, (q ≤ 10^5);
对于另外 20% 的数据, (p = 999983);
对于 100% 的数据, (a ≤ 10^9, q ≤ 10^7, p ≤ 10^9, ⌊frac{q}{k}⌋ ≤ 1000, b_0, l ≤ 10^{12}, m, c ≤ 10^6).
分析
定义两个数组s,t,s储存 (a^1,a^2,...,a^{1000000}) ,t储存 (a^{1000000},a^{2000000},...,a^{10^{12}}),每次的答案即为 (s[b_i\%1000000]*t[i/1000000]\%p) 。
Code
#include<cstdio>
#define maxn 1000001
using namespace std;
typedef long long D;
D mod,A[maxn+1],B[maxn+1];
D mul(D a,D b){return (a*=b)>=mod?a%mod:a;}
int main(){
D a,q,k,l,m,c,b,last,Xor=0;
scanf("%lld%lld%lld%lld%lld%lld%lld%lld",&a,&mod,&q,&k,&last,&l,&m,&c);
A[0]=1;
for(D i=1;i<=maxn;i++)A[i]=mul(A[i-1],a);
B[0]=1;
for(D i=1;i<=maxn;i++)B[i]=mul(B[i-1],A[maxn]);
for(D i=1;i<=q;i++){
b=(m*last+c)%l;
Xor^=mul(A[b%maxn],B[b/maxn]);
if(i%k==0)printf("%lld
",Xor);
last=b;
}
return 0;
}
2 树
时间限制: 1s
空间限制: 256MB
2.1 题目描述
你有一个长度为 (n) 的序列, 第 (i) 个数是 (a_i) , 下标从 (1) 开始. 有 (q) 次操作, 可能为:
1 l r k, 表示 (∀x ∈ [l, r]) , 使 (a_x) 变为 (a_x) & (k). 其中 & 表示按位与运算.
2 l r, 表示询问连续子序列 ([l, r]) 中所有元素的和.
3 l r, 表示询问: 如果在 ([l, r]) 之间均匀随机生成两个整数 (x, y,(a_x + a_y)^2) 的期望值. 你只需要输出答案与 ((r − l + 1)^2) 的乘积对 (998244353) 取模的值. 可以证明答案一定是整数.
2.2 输入格式
第一行一个整数 (n) 表示序列长度, 接下来一行 (n) 个整数描述这个序列.
第三行一个整数 (q) 表示操作次数, 接下来 (q) 行每行一次操作, 格式同题目描述.
2.3 输出格式
输出等同于操作 2, 3 次数之和的行数, 每行一个非负整数表示对应询问的答案. 注意操作 2 的答案不需要进行取模.
2.4 样例数据
2.4.1 样例 1 输入
5
8 4 3 5 6
5
2 3 5
3 1 2
1 2 4 3
2 3 5
3 1 2
2.4.2 样例 1 输出
14
608
10
384
2.4.3 样例 1 解释
第三次操作后, 序列变为 ([8, 0, 3, 1, 6]) .
2.5 数据范围
对于前 30% 的数据, (n, q ≤ 100);
对于另 20% 的数据, 没有操作 1;
对于另 20% 的数据, 没有操作 3;
对于 100% 的数据, (n, q ≤ 10^5, ai ≤ 10^9, k ≤ 2^30, 1 ≤ l ≤ r ≤ n) .
分析
2操作为线段树基本操作，3操作其实就是求 $$sum_{iin [x,y]}sum_{jin [x,y]}(a_i+a_j)^2$$ 它等于 $$2* ((y-x+1)* ([x,y]的平方和)+([x,y]的和)^2)$$
在每个节点维护一个和（ (sum_i a_i) ）与一个平方和（ (sum_ia_i^2) ）即可。
对于1操作，暴力 (O(n)) 修改（不用懒标记），不过要加一些剪枝：在每个节点维护一个或和，如果 要按位与的数 (k) 按位或上 这个或和 等于 (k) ，那么就没有必要修改此区间了。因为修改和不修改效果一样。
然后就 (AC) 了
Code
#include<cstdio>
#define maxn 100002
#define mod 998244353ll
#define ch1(p) (p<<1)
#define ch2(p) (p<<1|1)
using namespace std;
typedef long long D;
inline D Plus(D a,D b){return (a+b)%mod;}
inline D mul(D a,D b){return a*b%mod;}
D read(){
char c=getchar();
while(c<'0'||c>'9')c=getchar();
D x=0;
while(c>='0'&&c<='9'){
x=(x<<3)+(x<<1)+c-'0';
c=getchar();
}
return x;
}
void write(const D x){
if(x>=10)write(x/10);
putchar(x%10+'0');
}
D a[maxn],n;
struct node{
D sum,sqrsum,Or;
node():sum(0),sqrsum(0),Or(0){}
};
node t[maxn<<2];
void pushup(D p){
t[p].sum=t[ch1(p)].sum+t[ch2(p)].sum;
t[p].sqrsum=Plus(t[ch1(p)].sqrsum,t[ch2(p)].sqrsum);
t[p].Or=t[ch1(p)].Or|t[ch2(p)].Or;
}
void build(D p,D l,D r){
if(l==r){
t[p].sum=a[l];
t[p].sqrsum=mul(a[l]%mod,a[l]%mod);
t[p].Or=a[l];
return;
}
D mid=(l+r)>>1;
build(ch1(p),l,mid);
build(ch2(p),mid+1,r);
pushup(p);
}
void change(D p,D l,D r,D seg_l,D seg_r,D k){
if(l==r){
t[p].sum&=k;
t[p].sqrsum=mul(t[p].sum%mod,t[p].sum%mod);
t[p].Or=t[p].sum;
}
if(seg_l<=l&&r<=seg_r&&(t[p].Or|k)==k)return;
D mid=(l+r)>>1;
if(seg_l<=mid)change(ch1(p),l,mid,seg_l,seg_r,k);
if(seg_r>mid)change(ch2(p),mid+1,r,seg_l,seg_r,k);
pushup(p);
}
const D query1(D p,D l,D r,D seg_l,D seg_r){
if(seg_l<=l&&r<=seg_r){
return t[p].sum;
}
D mid=(l+r)>>1;
D ret=0;
if(seg_l<=mid)ret+=query1(ch1(p),l,mid,seg_l,seg_r);
if(seg_r>mid)ret+=query1(ch2(p),mid+1,r,seg_l,seg_r);
return ret;
}
const node query2(D p,D l,D r,D seg_l,D seg_r){
if(seg_l<=l&&r<=seg_r){
return t[p];
}
D mid=(l+r)>>1;
node ret;
if(seg_l<=mid&&seg_r>mid){
node tmp1=query2(ch1(p),l,mid,seg_l,seg_r),tmp2=query2(ch2(p),mid+1,r,seg_l,seg_r);
ret.sum=Plus(tmp1.sum%mod,tmp2.sum%mod);
ret.sqrsum=Plus(tmp1.sqrsum,tmp2.sqrsum);
}
else{
if(seg_l<=mid)ret=query2(ch1(p),l,mid,seg_l,seg_r);
if(seg_r>mid)ret=query2(ch2(p),mid+1,r,seg_l,seg_r);
ret.sum%=mod;
}
return ret;
}
signed main(){
n=read();
for(D i=1;i<=n;i++)a[i]=read();
build(1,1,n);
D q=read(),mo,x,y,k;
while(q--){
mo=read(),x=read(),y=read();
if(mo==1){
k=read();
change(1,1,n,x,y,k);
}
else if(mo==2){
write(query1(1,1,n,x,y));
putchar('
');
}
else{
node tmp=query2(1,1,n,x,y);
write(mul(2,Plus(mul(y-x+1,tmp.sqrsum),mul(tmp.sum%mod,tmp.sum%mod))));
putchar('
');
}
}
return 0;
}