期望得分：55+24+53
实际得分：0+0+3
乐死
累加变量清零了吗？
打出更高的部分分暴力删了吗？
样例解释换行你看见了吗？
T1 Prime
打出55分做法没删原来的暴力，结果就轻松挂55分
考场上想到根号的预处理，但是并未想到如何进行映射
正解是先预处理$[1,\sqrt R]$中的类素数，然后标记他们在$[L,R]$间的倍数
剩下的就是答案
1 #include<bits/stdc++.h>
2 #define int long long
3 using namespace std;
4 namespace AE86{
5 inline int read(){
6 int x=0,f=1;char ch=getchar();
7 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
8 while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;
9 }inline void write(int x,char opt='\n'){
10 char ch[20];int len=0;if(x<0)x=~x+1,putchar('-');
11 do{ch[len++]=x%10+(1<<5)+(1<<4);x/=10;}while(x);
12 for(int i=len-1;i>=0;--i)putchar(ch[i]);putchar(opt);}
13 }using namespace AE86;
14
15 const int NN=1e7+5;
16 int l,r,k,ans,fan;
17 int prime[NN],len;
18 bool vis[NN],tag[NN];
19 inline void getprime(int n){
20 for(int i=2;i<=n;++i){
21 if(!vis[i]) prime[++len]=i;
22 for(int j=1;prime[j]*i<=n&&j<=len&&prime[j]<=k;++j){
23 vis[prime[j]*i]=1;
24 if(prime[j]%i==0) break;
25 }
26 }
27 for(int i=1;i<=len;i++){
28 int j=ceil(1.0*l/prime[i]);
29 j=max(j,2ll);
30 while(j*prime[i]<=r){
31 tag[j*prime[i]-l]=1;
32 j++;
33 }
34 }
35 }
36 namespace WSN{
37 inline short main(){
38 l=read(); r=read(); k=read(); fan=min(k,(int)sqrt(r));
39 getprime(fan);
40 for(int i=l;i<=r;i++) if(!tag[i-l]) ans^=i;
41 write(ans);return 0;
42 return 0;
43 }
44 }
45 signed main(){return WSN::main();}
View Code
T2 Sequence
神仙的矩阵快速幂。
考虑设$dp_x$为子序列最后一个数是$x$的方案数，我们先$O(n)$预处理出前面$n$个的
$dp$值，将其按照先后出现的顺序升序排列构造出$k*1$的一个矩阵
考虑之后如何高效转移，发现向量矩阵里面的值转移时值大的会覆盖小的，那么方便转移应该将转移矩阵赋值为
0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 1 1 1 1 1 0 0 0 0 1
这样可以满足方程式$dp_x=(\sum_{i=1}^{k}dp_i)+1$
复杂度$O(n+k^3logm)$应该懂我在表达什么（
T3 Omeed
可以转化$base=\sum p_i*A,comb=\sum p_i*(f_{i-1}+1)$ 其中$f_i$表示$comb_i$的期望
可以递推来求：$f_i=(f_{i-1}+1)*p_i+f_{i-1}*(1-p_i)$
线段树上分别维护关于$comb$的求解系数，单个$comb$的求解系数，比较麻烦
需要保证区间合并的时候，他的答案应该能用之前$f_{L-1}$配合$k,b$表示出
这一步需要稍微转化一波柿子
然而正常人敲出正解后应该只有$89$分，剩下的就要耐心的卡常
1 #include<bits/stdc++.h>
2 #define lid (id<<1)
3 #define rid (id<<1|1)
4 #define mod 998244353
5 using namespace std;
6 namespace AE86{
7 inline int read(){
8 int x=0,f=1;char ch=getchar();
9 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
10 while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;
11 }inline void write(long long x,char opt='\n'){
12 char ch[20];int len=0;if(x<0)x=~x+1,putchar('-');
13 do{ch[len++]=x%10+(1<<5)+(1<<4);x/=10;}while(x);
14 for(int i=len-1;i>=0;--i)putchar(ch[i]);putchar(opt);}
15 }using namespace AE86;
16 const int NN=5e5+5;
17 int n,q,ta,tb,A,B,t,p[NN],p1[NN],p2[NN];
18 struct SNOW{int sum,k,b,ans,xi;};
19 inline int qmo(int a){int ans=1,c=mod,b=mod-2; a%=c;while(b){if(b&1) ans=1ll*ans*a%c;b>>=1;a=1ll*a*a%c;}return ans;}
20
21 namespace SNOWtree{
22 int ll[NN<<2],rr[NN<<2];
23 int k[NN<<2],b[NN<<2],xi[NN<<2];
24 int sk[NN<<2],sb[NN<<2];
25 int sum[NN<<2],ans[NN<<2];
26 inline void pushup(int id){
27 if(ll[id]==rr[id]) return;
28 sum[id]=(sum[lid]+sum[rid])%mod;
29 xi[id]=(1ll*xi[lid]+1ll*xi[rid]*k[lid]%mod)%mod;
30 k[id]=1ll*k[lid]*k[rid]%mod;
31 b[id]=(1ll*b[lid]*k[rid]%mod+1ll*b[rid])%mod;
32 ans[id]=(1ll*b[lid]*xi[rid]%mod+ans[rid]+ans[lid])%mod;
33 }
34 inline void build(int id,int l,int r){
35 ll[id]=l; rr[id]=r;
36 if(l==r){
37 sum[id]=p[l]%mod;
38 k[id]=(p[l]+t-1ll*p[l]*t%mod+mod)%mod;
39 b[id]=p[l]; ans[id]=xi[id]=p[l];
40 return;
41 }int mid=l+r>>1;
42 build(lid,l,mid); build(rid,mid+1,r);
43 pushup(id);
44 }
45 inline void update(int id,int pos){
46 if(ll[id]==rr[id]){
47 int val=p[ll[id]];
48 sum[id]=val%mod;
49 k[id]=(val+t-1ll*val*t%mod+mod)%mod;
50 b[id]=val; ans[id]=xi[id]=val;
51 return;
52 }int mid=ll[id]+rr[id]>>1;
53 if(pos<=mid) update(lid,pos);
54 else update(rid,pos);
55 pushup(id);
56 }
57 inline SNOW found(int id,int l,int r){
58 if(l<=ll[id]&&rr[id]<=r)return(SNOW){sum[id],k[id],b[id],ans[id],xi[id]};
59 int mid=ll[id]+rr[id]>>1;SNOW tmp1={0,0,0,0,0},tmp2={0,0,0,0,0};
60 if(l<=mid) tmp1=found(lid,l,r);
61 if(r>mid) tmp2=found(rid,l,r);
62 return (SNOW){
63 (1ll*tmp1.sum+tmp2.sum)%mod,
64 (1ll*tmp1.k*tmp2.k)%mod,
65 (1ll*tmp1.b*tmp2.k%mod+tmp2.b)%mod,
66 (1ll*tmp1.ans+tmp2.ans+1ll*tmp1.b*tmp2.xi%mod)%mod,
67 (1ll*tmp1.xi+1ll*tmp2.xi*tmp1.k%mod)%mod
68 };
69 }
70 }using namespace SNOWtree;
71
72 namespace WSN{
73 inline short main(){
74 read(); n=read();q=read(); if(!q) return 0;
75 ta=read();tb=read(); A=read()%mod;B=read()%mod;
76 t=1ll*ta*qmo(tb)%mod;
77 for(int i=1,p1,p2;i<=n;i++)
78 p1=read(),p2=read(),p[i]=1ll*p1*qmo(p2)%mod;
79 build(1,1,n);
80 while(q--){
81 int opt=read();
82 if(opt==0){
83 int x=read(),wa=read(),wb=read();
84 int w=1ll*wa*qmo(wb)%mod; p[x]=w;
85 update(1,x);
86 }
87 if(opt==1){
88 int l=read(),r=read();
89 SNOW tmp=found(1,l,r);
90 write((1ll*A*tmp.sum%mod+1ll*B*tmp.ans%mod)%mod);
91 }
92 }
93 return 0;
94 }
95 }
96 signed main(){return WSN::main();}
View Code