contest0111

模拟赛

弹珠

平衡树维护出序列;

后面部分使用单调栈维护下凸壳即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
/*
>Author: zxy_hhhh
>blog: zxy-hhhh.cn
>date: 2019/01/11
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<cmath>
#define rep(x,a,b) for (int x=int(a);x<=(int)(b);x++)
#define drp(x,a,b) for (int x=int(a);x>=(int)(b);x--)
#define cross(x,a) for (int x=hd[a];x;x=nx[x])
#define ll long long
using namespace std;
inline ll rd()
{
ll _x=0;int _ch=getchar(),_f=1;
for(;!isdigit(_ch)&&(_ch!='-')&&(_ch!=EOF);_ch=getchar());
if (_ch=='-'){_f=0;_ch=getchar();}
for(;isdigit(_ch);_ch=getchar()) _x=_x*10+_ch-'0';
return _f?_x:-_x;
}
void write(ll _x){if (_x>=10) write(_x/10),putchar(_x%10+'0'); else putchar(_x+'0'); }
inline void wrt(ll _x,char _p){if (_x<0) putchar('-'),_x=-_x; write(_x); if (_p) putchar(_p);}
#define maxn 500005
#define maxval 1000000000
namespace Treap {
int sz[maxn],ls[maxn],rs[maxn],fix[maxn],val[maxn],cnt,rt;
inline void pushup(int x) {sz[x]=sz[ls[x]]+sz[rs[x]]+1;}
inline int new_node(int x) {
sz[++cnt]=1,ls[cnt]=rs[cnt]=0,fix[cnt]=rand(),val[cnt]=x;
return cnt;
}
inline int merge(int x,int y) {
if (!x||!y) return x+y;
if (fix[x]<fix[y]) {rs[x]=merge(rs[x],y),pushup(x);return x;}
else {ls[y]=merge(x,ls[y]),pushup(y);return y;}
}
inline void split(int pos,int k,int &x,int &y) {
if (!pos) return x=y=0,void();
if (sz[ls[pos]]>=k) y=pos,split(ls[pos],k,x,ls[y]),pushup(y);
else x=pos,split(rs[pos],k-sz[ls[pos]]-1,rs[x],y),pushup(x);
}
inline int find(int k) {
int now=rt;
while(1){
if (sz[ls[now]]>=k) now=ls[now];
else if (sz[ls[now]]+1==k) return now;
else k=k-sz[ls[now]]-1,now=rs[now];
}
}
inline void update(int t,int v) {
int x=find(t+1);
val[x]=v;
}
inline void insert(int t,int v) {
int x,y,z;
split(rt,t,x,y);
rt=merge(x,merge(new_node(v),y));
}
inline int query(int t) {
int x=find(t);
return val[x];
}
}
int n,m;
int q[maxn],p[maxn],H[maxn<<1],a[maxn];
int w[maxn],sta[maxn],top;
inline int find(int x,int y)
{
return (q[x]-q[y])/(p[y]-p[x]);
}
inline int push(int x)
{
while(find(x,sta[top])>=w[top]&&top) top--;
if (top==0) sta[++top]=x,w[top]=maxval;
else sta[++top]=x,w[top]=find(x,sta[top-1]);
}
inline int Pos(int x)
{
int l=1,r=top,ans;
while(l<=r){
int mid=(l+r)>>1;
if (x<=w[mid]) l=mid+1,ans=mid;
else r=mid-1;
}
return sta[ans];
}
int main()
{
n=rd(),m=rd();
char s[10];
rep(i,1,m){
scanf("%s",s+1);
if (s[1]=='I'){
int x=rd(),val=rd();
Treap::insert(x,val);
}
else {
int x=rd(),val=rd();
Treap::update(x,val);
}
}
rep(i,1,n) p[i]=-rd(),q[i]=rd(),a[i]=Treap::query(i);
int tot=0;
rep(i,1,n) {
H[++tot]=a[i];
if (i>1) H[++tot]=find(i,i-1);
}
sort(H+1,H+1+tot);
push(1);
rep(i,2,n){
int w=Pos(a[i]);
ll Ans=1ll*p[w]*a[i]+(ll)q[w];
//wrt(w,' ');
//rep(j,1,i-1) printf("%d %d %lld\n",i,j,(ll)p[j]*a[i]+q[j]);
wrt(max(Ans,0ll),'\n');
push(i);
}
}

数学

打表可知

$Ans=n×m×\varphi(n)×\varphi(m)$

直接使用

$\varphi(n)=n\prod\limits \frac{p_k-1}{p_k}$ $p_k$是$n$的因子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/*
>Author: zxy_hhhh
>blog: zxy-hhhh.cn
>date: 2019/01/11
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<cmath>
#define rep(x,a,b) for (int x=int(a);x<=(int)(b);x++)
#define drp(x,a,b) for (int x=int(a);x>=(int)(b);x--)
#define cross(x,a) for (int x=hd[a];x;x=nx[x])
#define ll long long
using namespace std;
inline ll rd()
{
ll _x=0;int _ch=getchar(),_f=1;
for(;!isdigit(_ch)&&(_ch!='-')&&(_ch!=EOF);_ch=getchar());
if (_ch=='-'){_f=0;_ch=getchar();}
for(;isdigit(_ch);_ch=getchar()) _x=_x*10+_ch-'0';
return _f?_x:-_x;
}
void write(ll _x){if (_x>=10) write(_x/10),putchar(_x%10+'0'); else putchar(_x+'0'); }
inline void wrt(ll _x,char _p){if (_x<0) putchar('-'),_x=-_x; write(_x); if (_p) putchar(_p);}
#define maxn 40000005
#define mod 998244353
int pri[maxn],tp;
bool vis[maxn];
inline void euler(int mx)
{
rep(i,2,mx){
if (!vis[i]) pri[++tp]=i;
for(int j=1;pri[j]*i<=mx;j++){
vis[i*pri[j]]=1;
if (i%pri[j]==0) break;
}
}
}
ll num[1000005];
inline ll phi(ll x)
{
ll ans=x,X=x;
int tot=0;
for(int i=1;i<=tp&&pri[i]<=x;i++)if (x%pri[i]==0){
num[++tot]=pri[i];
x/=pri[i];
while(x%pri[i]==0) x/=pri[i];
}
if (x>1) num[++tot]=x;
rep(i,1,tot) ans=ans/num[i];
rep(i,1,tot) ans=ans*(num[i]-1);
return ans;
}
int main()
{
euler(3222776);
ll n=rd(),m=rd();
wrt((n%mod)*(m%mod)%mod*(phi(n)%mod)%mod*(phi(m)%mod)%mod,'\n');
}

tty 的求助

公式考场上没推出来QwQ,公式推导参考这里

然后我的计算方法不是数论分块,可以直接暴力计算,复杂度是调和级数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
/*
>Author: zxy_hhhh
>blog: zxy-hhhh.cn
>date: 2019/01/11
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<cmath>
#define rep(x,a,b) for (int x=int(a);x<=(int)(b);x++)
#define drp(x,a,b) for (int x=int(a);x>=(int)(b);x--)
#define cross(x,a) for (int x=hd[a];x;x=nx[x])
#define ll long long
using namespace std;
inline ll rd()
{
ll _x=0;int _ch=getchar(),_f=1;
for(;!isdigit(_ch)&&(_ch!='-')&&(_ch!=EOF);_ch=getchar());
if (_ch=='-'){_f=0;_ch=getchar();}
for(;isdigit(_ch);_ch=getchar()) _x=_x*10+_ch-'0';
return _f?_x:-_x;
}
void write(ll _x){if (_x>=10) write(_x/10),putchar(_x%10+'0'); else putchar(_x+'0'); }
inline void wrt(ll _x,char _p){if (_x<0) putchar('-'),_x=-_x; write(_x); if (_p) putchar(_p);}
#define maxn 5000005
#define mod 998244353
int mu[maxn],pri[maxn],tp;
bool vis[maxn];
inline void euler(int mx)
{
mu[1]=1;
rep(i,2,mx){
if (!vis[i]) pri[++tp]=i,mu[i]=-1;
for(int j=1;j<=tp&&pri[j]*i<=mx;j++){
vis[i*pri[j]]=1;
if (i%pri[j]==0){
mu[i*pri[j]]=0;
break;
}
else mu[i*pri[j]]=mu[i]*(-1);
}
}
}
inline ll solve(int N,int M,int x)
{
int mx1=min(N,M);
euler(mx1);
ll ans=0;
rep(d,1,mx1){
int mx2=min(N/d,M/d);
ll res=0;
rep(t,1,mx2)
res+=mu[t]*(N/(1ll*t*d))*(M/(1ll*t*d)),
res=res%mod;
ans=(ans+(2ll*d*(x/d)%mod+d)%mod*res)%mod;
}
return ans;
}
#define inv2 499122177
inline ll S(int x)
{
return 1ll*x*(x+1)%mod*inv2%mod;
}
int main()
{
int N=rd(),M=rd(),x=rd();
ll ans=solve(N,M,x);
ans=ans+S(N)*S(M)%mod;
ans=ans-S(M)*N%mod;
ans=ans-S(N)*M%mod;
ans=ans%mod;
ans=ans<0?ans+mod:ans;
ans=ans*inv2%mod;
wrt(ans,'\n');
}
avatar
杜教筛

  1. 1. 弹珠
  2. 2. 数学
  3. 3. tty 的求助