乐死

累加变量清零了吗？

打出更高的部分分暴力删了吗？

样例解释换行你看见了吗？

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();}

T2 Sequence

神仙的矩阵快速幂。

考虑设$dp_x$为子序列最后一个数是$x$的方案数，我们先$O(n)$预处理出前面$n$个的

$dp$值，将其按照先后出现的顺序升序排列构造出$k*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();}

巴特西

Noip模拟47 2021.8.25

乐死