| Solved | A | B | C | D | E | F | G | H | I | J | K | L |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 10/12 | O | O | O | O | O | ! | O | . | Ø | O | O | O |
- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet
A
题目描述
给一个小写字母串，问最少修改多少次能使串所有奇数长度的子串都为回文串。
解题思路
solved by qxforever
答案只有$ababa$和$aaaaa$两种情况，分别枚举$a$，$b$即可。
AC代码 - by qxforever
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
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e5+23;
int n,m,T;
char s[maxn];
int main()
{
cin>>T;
while(T--){
scanf("%s",s);
int ans=1e9;
for(char i='a';i<='z';i++){
for(char j='a';j<='z';j++){
int now=0;
for(int k=0;s[k];k++){
if(k%2==0&&s[k]!=i) now++;
if(k%2==1&&s[k]!=j) now++;
}
ans=min(ans,now);
}
}
printf("%d\n",ans);
}
}
B
题目描述
给定一组$p_i,k_i$，$n=\Pi_{i}p_i^{k_i}$，求$\sum_{d|n}\phi(d)\times \frac nd\text{ mod 998244353}$。
解题思路
两个积性函数的狄利克雷卷积仍为积性函数。对于每个$p_i$推推式子求一下即可。
AC代码
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
typedef long long ll;
using namespace std;
const ll mod=998244353;
ll qp(ll a,int p){
ll ans=1;
for(;p;p>>=1,a=a*a%mod)if(p&1)ans=ans*a%mod;
return ans;
}
int main(){
int i,t,m;
scanf("%d",&t);
while(t--){
ll ans=1;
scanf("%d",&m);
while(m--){
ll p,k,t;
scanf("%lld%lld",&p,&k);
t=qp(p,k-1)*(p+k*(p-1)%mod)%mod;
ans=ans*t%mod;
}
printf("%lld\n",ans);
}
return 0;
}
C
题目描述
两个人玩$Nim$游戏，其中一个人在没拿完石头的情况下需要拿两次石头。给定先后手顺序和石子情况，问谁能赢。
解题思路
$Nim$变体常见套路：先讨论全$1$情况，再讨论$>1$个数$=1$的情况，再讨论多个$>1$的情况。
AC代码
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
typedef long long ll;
using namespace std;
int main(){
int i,t,n,d;
scanf("%d",&t);
while(t--){
int cnt=0,x;
scanf("%d%d",&n,&d);
for(i=1;i<=n;i++)scanf("%d",&x),cnt+=x>1;
if(!cnt)printf("%s\n",((d==1)&&(n%3))||((d==2)&&((n-1)%3))?"Yes":"No");
else if(cnt==1)printf("%s\n",(d==1)||(n%3==2)?"Yes":"No");
else printf("Yes\n");
}
return 0;
}
D
题目描述
给一棵点权树，其中第$i$个节点的父亲等概率地是$[1,i-1]$中的任意一个。随机挑选一个点，问这个点的子树和的期望是多少。
解题思路1
solved by nikkukun
易证结论：对于任意$i$和任意$j>i$，$j$作为$i$子树的概率为$\frac 1i$。于是$i$的子树和期望为$a_i+\frac{a_{i+1}+a_{i+2}+…+a_n}{i}$，再对所有的$i$求一下均值即可。
AC代码
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
typedef long long ll;
using namespace std;
int a[N],s[N],inv[N];
const ll mod=998244353;
int main(){
int i,T,n;
inv[0]=inv[1]=1;
scanf("%d",&T);
for(i=2;i<N;i++)inv[i]=inv[mod%i]*(mod-mod/i)%mod;
while(T--){
ll ans=0;
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d",&a[i]);
s[i]=(s[i-1]+a[i])%mod;
}
for(i=1;i<=n;i++)(ans+=1LL*(s[n]-s[i])*inv[i]+a[i])%=mod;
printf("%lld\n",ans*inv[n]%mod);
}
return 0;
}
解题思路2
solved by qxforever
对于一个点$i$，在所有$n$个点的子树中出现的次数就是它的深度期望$dep_i$，故答案就是$\frac{\sum_{i}a_idep_i}n$，而$dep_i=\frac{\sum_{j<i}dep_j}{i-1}+1$。
AC代码
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
typedef long long ll;
using namespace std;
int a[N],d[N],inv[N];
const ll mod=998244353;
int main(){
int i,T,n;
inv[0]=inv[1]=1;
scanf("%d",&T);
for(i=2;i<N;i++)inv[i]=inv[mod%i]*(mod-mod/i)%mod;
while(T--){
ll sd=0,ans=0;
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d",&a[i]);
if(i==1)d[i]=1;
else d[i]=(sd*inv[i-1]+1)%mod;
(sd+=d[i])%=mod;
}
for(i=1;i<=n;i++)(ans+=1LL*a[i]*d[i])%=mod;
printf("%lld\n",ans*inv[n]%mod);
}
return 0;
}
E
题目描述
给一个$n$个点的点权树，问对于所有的$i\in[1,m]$，是否有一个连通子图满足权重之和为$i$。
$n\leq 3000,m\leq 100000,T\leq 15$。
解题思路
显然的点分治，合并子树情况时使用$bitset$，复杂度$O(T\frac{n^2}{64}\log n)$。
AC代码
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
typedef long long ll;
using namespace std;
struct Edge{
int end,near;
}e[N<<1];
int head[N],cnt;
void add(int a,int b){
e[++cnt].end=b;
e[cnt].near=head[a];
head[a]=cnt;
}
int vis[N],siz[N],mxt[N];
int rt,sum,n,m;
void getrt(int v,int fa){
int i;
siz[v]=1;mxt[v]=0;
for(i=head[v];i;i=e[i].near){
int p=e[i].end;
if(p==fa||vis[p])continue;
getrt(p,v);
siz[v]+=siz[p];
mxt[v]=max(mxt[v],siz[p]);
}
mxt[v]=max(mxt[v],sum-siz[v]);
if(mxt[v]<mxt[rt])rt=v;
}
int w[N];
bitset<M>b[N],res;
void getdis(int v,int fa){
int i;
b[v]<<=w[v];
for(i=head[v];i;i=e[i].near){
int q=e[i].end;
if(q==fa||vis[q])continue;
b[q]=b[v];
getdis(q,v);
b[v]|=b[q];
}
}
void sol(int v){
vis[v]=1;
int i;
b[v].reset();
b[v][0]=1;
getdis(v,0);
res|=b[v];
for(i=head[v];i;i=e[i].near){
int q=e[i].end;
if(vis[q])continue;
sum=siz[q];
mxt[0]=n;
rt=0;
getrt(q,0);
sol(rt);
}
}
int main(){
int i,a,b,c,T;
scanf("%d",&T);
while(T--){
res.reset();
memset(head,0,sizeof(head));cnt=0;
memset(vis,0,sizeof(vis));
scanf("%d%d",&n,&m);
for(i=1;i<n;i++){
scanf("%d%d",&a,&b);
add(a,b),add(b,a);
}
for(i=1;i<=n;i++)scanf("%d",&w[i]);
sum=n;mxt[0]=n;
getrt(1,0);
sol(rt);
for(i=1;i<=m;i++)printf("%d",res[i]==1);
puts("");
}
return 0;
}
F
题目描述
解题思路
AC代码
2
G
题目描述
$n$个城市，第$i$个城市里有$a_i$个男的，$b_i$个女的，$\sum_ia_i=\sum_ib_i$。
问有多少种婚配方法满足所有人都有且仅有一个对象，且与对方互不同城。
解题思路
首先容易想到，设$f(i)$表示至少有$i$对同城的方案数，设$tot=\sum_{i}a_i$，容斥一下答案为$\sum_{i=0}^{tot}f(i)(-1)^{i}$。
考虑求$f(i)$，也就是钦定$i$对同城关系的方案数。
设$g(j,k)$表示第$j$个城市中钦定$k$对的方案数，有$f(i)=(tot-i)!\sum_{\sum_{k_j}=i}\Pi_{j}g(j,k_j)$。这是一个卷积的形式，把所有城市依次卷起来即可。而$g(j,k)$易求，为$C_{a_j}^{k}C_{b_j}^{k}k!$。
于是$NTT/$拆系数$FFT$即可求解，每次拿出次数最小的两项卷积即可。
注意！！！$\text{priority_queue}$是大顶堆！！！
AC代码
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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
typedef long long ll;
using namespace std;
const int mod=998244353;
/*struct comp{
double x,y;
comp():x(0),y(0){}
comp(const double &_x,const double &_y):x(_x),y(_y){}
};
comp operator+(const comp &a,const comp &b){
return comp(a.x+b.x,a.y+b.y);
}
comp operator-(const comp &a,const comp &b){
return comp(a.x-b.x,a.y-b.y);
}
comp operator*(const comp &a,const comp &b){
return comp(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);
}
comp conj(const comp &a){return comp(a.x,-a.y);}
double PI=acos(-1);
comp w[M+5];
int rev[M+5];*/
int A[M+5],B[M+5],C[M+5],lim,mx;
const int maxl = 22;
const int maxn = 1<< maxl;
//const int mod = 998244353;
int rev[M+5];
int qpow(int a,int b){
int ans=1;
while(b){
if(b&1)ans=1ll*ans*a%mod;
a=1ll*a*a%mod;
b>>=1;
}
return ans;
}
void transform(int n,int *t,int typ){
for(int i=0;i<n;i++)
if(i<rev[i])swap(t[i],t[rev[i]]);
for(int step=1;step<n;step<<=1){
int gn=qpow(3,(mod-1)/(step<<1));
for(int i=0;i<n;i+=(step<<1)){
int g=1;
for(int j=0;j<step;j++,g=1ll*g*gn%mod){
int x=t[i+j],y=1ll*g*t[i+j+step]%mod;
t[i+j]=(x+y)%mod;
t[i+j+step]=(x-y+mod)%mod;
}
}
}
if(typ==1)return;
for(int i=1;i<n/2;i++)swap(t[i],t[n-i]);
int inv=qpow(n,mod-2);
for(int i=0;i<n;i++)t[i]=1ll*t[i]*inv%mod;
}
void ntt(int p,int *A,int *B,int *C){
transform(p,A,1);
transform(p,B,1);
for(int i=0;i<p;i++)C[i]=1ll*A[i]*B[i]%mod;
transform(p,C,-1);
}
/*void fft(comp *a,int n){
int i,j,k,lyc;
for(i=0;i<n;i++)if(i<rev[i]) swap(a[i],a[rev[i]]);
for(i=2,lyc=n>>1;i<=n;i<<=1,lyc>>=1)
for(j=0;j<n;j+=i){
comp *l=a+j,*r=a+j+(i>>1),*p=w;
for(k=0;k<(i>>1);k++){
comp tmp=*r**p;
*r=*l-tmp,*l=*l+tmp;
++l,++r,p+=lyc;
}
}
}
void fft_prepare(){
int i;
for(i=0;i<lim;i++)rev[i]=rev[i>>1]>>1|((i&1)<<(mx-1));
for(i=0;i<lim;i++)w[i]=comp(cos(2*PI*i/lim),sin(2*PI*i/lim));
}
comp a[M+5],b[M+5],ta[M+5],tb[M+5];
void conv(int *x,int *y,int *z){
int i,j;
for(i=0;i<lim;i++)(x[i]+=mod)%=mod,(y[i]+=mod)%=mod;
for(i=0;i<lim;i++){
ta[i]=comp(x[i]&32767,x[i]>>15);
tb[i]=comp(y[i]&32767,y[i]>>15);
}
fft(ta,lim);fft(tb,lim);
for(i=0;i<lim;i++){
j=(lim-i)%lim;//0的特判
comp da,db,dc,dd;
da=(ta[i]+conj(ta[j]))*comp(0.5,0);
db=(ta[i]-conj(ta[j]))*comp(0,-0.5);
dc=(tb[i]+conj(tb[j]))*comp(0.5,0);
dd=(tb[i]-conj(tb[j]))*comp(0,-0.5);
a[j]=da*dc+da*dd*comp(0,1);
b[j]=db*dc+db*dd*comp(0,1);
}
fft(a,lim);fft(b,lim);
for(i=0;i<lim;i++){
ll da,db,dc,dd;
da=(ll)(a[i].x/lim+0.5)%mod;
db=(ll)(a[i].y/lim+0.5)%mod;
dc=(ll)(b[i].x/lim+0.5)%mod;
dd=(ll)(b[i].y/lim+0.5)%mod;
z[i]=(da+((db+dc)<<15)+(dd<<30))%mod;
}
}*/
ll fac[N],invs[N],inv[N];
priority_queue<pii>Q;//fi:sz se:id
vector<int>v[N];
void conv(vector<int>&v1,vector<int>&v2,pii&p){
int i,n=v1.size(),m=v2.size();
mx=0;
while((1<<mx)<n+m-1)mx++;
lim=1<<mx;
for(i=0;i<n;i++)A[i]=v1[i];
for(;i<lim;i++)A[i]=0;
for(i=0;i<m;i++)B[i]=v2[i];
for(;i<lim;i++)B[i]=0;
for(i=0;i<lim;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(mx-1));
//fft_prepare();
//memset(C,0,sizeof(C));
ntt(lim,A,B,C);
//conv(A,B,C);
v1.clear();
v1.resize(n+m);
for(i=0;i<n+m-1;i++)v1[i]=C[i];
p.fi=-(n+m-1);
}
ll c(int n,int m){
if(n<0||m>n)return 0;
return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int main(){
int i,j,t;
scanf("%d",&t);
fac[0]=inv[0]=invs[0]=invs[1]=1;
for(i=1;i<=100000;i++){
fac[i]=fac[i-1]*i%mod;
if(i>1)invs[i]=invs[mod%i]*(mod-mod/i)%mod;
inv[i]=inv[i-1]*invs[i]%mod;
}
while(t--){
ll ans=0;
int tot=0,n;
while(!Q.empty())Q.pop();
scanf("%d",&n);
for(i=1;i<=n;i++)v[i].clear();
for(i=1;i<=n;i++){
int boy,gir,mn;
scanf("%d%d",&boy,&gir);
tot+=boy;mn=min(boy,gir);
v[i].resize(mn+1);
for(j=0;j<=mn;j++){
ll temp=c(boy,j)*c(gir,j)%mod*fac[j]%mod;
v[i][j]=temp;
}
Q.push(mp(-v[i].size(),i));
}
while(Q.size()>=2){
pii pa=Q.top();Q.pop();
pii pb=Q.top();Q.pop();
pii pc=mp(0,pa.se);
//printf("a:%d\n",pa.se);
//for(auto p:v[pa.se])printf("%d ",p);printf("\nb:%d\n",pb.se);
//for(auto p:v[pb.se])printf("%d ",p);puts("");
conv(v[pa.se],v[pb.se],pc);
Q.push(pc);
}
pii fin=Q.top();Q.pop();
//printf("fin:%d\n",fin.se);
//for(auto p:v[fin.se])printf("%d ",p);puts("");
int flag=1;
for(i=0;i<-fin.fi;i++){
(ans+=flag*fac[tot-i]*v[fin.se][i]%mod)%=mod;
flag=-flag;
}
printf("%lld\n",(ans+mod)%mod);
}
return 0;
}
H
题目描述
解题思路
AC代码
2
I
题目描述
给一个$n\times m$的矩阵$a$，每个格点上有一个数字$a_{ij}$。可以花费$w_{ij}$去把$a_{ij}$变为$\lfloor\frac{a_{ij}}2\rfloor$，且可以进行任意多次。
给定一些相邻两个格子的取值要求$a_{x_1y_1}+a_{x_2y_2}\leq d_i$，$a_{x_1y_1}+a_{x_2y_2}\geq c_i$，问要满足这些要求的最小花费是多少。
解题思路
十分巧妙的一道题。首先容易想到，对每个格点$p$拆成$P+1$个子点，第$i(0\leq i\leq P)$个子点表示操作了$i$次这个格点，根据数据范围容易知道$P=15$即可表示所有情况。再将整个矩阵黑白染色，取值要求转化为在图上的一些边。这是一个最小割问题，故可以再假设，选了第$i$个子点就是割掉了某条长度为$iw_{p}$的边。
为方便起见，下面设$(x_1,y_1)$为白点$p$，$(x_2,y_2)$为黑点$q$。
第一类限制$a_{x_1y_1}+a_{x_2y_2}\leq d_i$的意思是，对于$p$的第$i$个子点和$q$的第$j$个子点，如果有$val_i+val_j> d$，那么必然在割掉$p_i$边的时候不可以只割掉$q_j$对应边。
第二类限制$a_{x_1y_1}+a_{x_2y_2}\geq c_i$的意思是，对于$p$的第$i$个子点和$q$的第$j$个子点，如果有$val_i+val_j< c$，那么必然在割掉$q_j$边的时候不可以割掉$p_i$对应边。
所以就可以由此建图：对于白点，$s\rightarrow p_0\rightarrow p_1…\rightarrow p_P\rightarrow t$，流量分别为$\inf,0,w_p,2w_p,…,14w_p,\inf$；对于黑点，$s\rightarrow p_P… p_1\rightarrow p_0\rightarrow s$，流量分别为$\inf,14w_p,…,w_p,0,\inf$。
对于第一类限制，对于白点的第$i$个子点，设$j$为最小的满足条件的黑点的子点，对于所有的$k<j$都需要满足“在割掉$p_i$时割掉$q_k$没有作用”，故连接$q_{j}\rightarrow p_i$，权为$\inf$。
对于第二类限制，对于黑点的第$i$个子点，设$j$为最大的满足条件的白点的子点，对于所有的$k>j$都需要满足“在割掉$q_i$时割掉$p_k$没有作用”，故连接$p_{j}\rightarrow q_i$，权为$\inf$。
注：上面的点只是起到理解的作用，实际实现会有一些左右的偏移。然后跑一遍最小割这题就做完了。
AC代码
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
typedef long long ll;
using namespace std;
struct Edge{
int l,e,n;
}e[M<<3];
int hd[M],cur[M],cnt=1;
void add(int a,int b,int l){
e[++cnt].e=b;e[cnt].l=l;e[cnt].n=hd[a];hd[a]=cnt;
e[++cnt].e=a;e[cnt].l=0;e[cnt].n=hd[b];hd[b]=cnt;
}
int inf=1e9,n,m,s,t;
int id(int x,int y,int k){return ((x-1)*m+y-1)*(P+1)+k+1;}
int dep[M];
queue<int>Q;
int dfs(int p,int flow){
if(p==t)return flow;
int i;
for(i=cur[p];i;i=e[i].n){
int q=e[i].e;
cur[p]=i;
if(dep[q]==1+dep[p]&&e[i].l){
int ans=dfs(q,min(flow,e[i].l));
if(ans>0){
e[i].l-=ans;
e[i^1].l+=ans;
return ans;
}
}
}
return 0;
}
int bfs(){
memset(dep,0,sizeof(dep));
Q.push(s);dep[s]=1;
int i;
while(!Q.empty()){
int p=Q.front();Q.pop();
for(i=hd[p];i;i=e[i].n){
int q=e[i].e;
if(!dep[q]&&e[i].l)dep[q]=dep[p]+1,Q.push(q);
}
}
return dep[t];
}
ll dinic(){
int i,d;
ll ans=0;
while(bfs()){
for(i=0;i<=t;i++)cur[i]=hd[i];
while((d=dfs(s,inf)))ans+=d;
}
return ans;
}
int a[N][N][P+2],v[N][N];
int main(){
int i,j,k,T,q;
scanf("%d",&T);
while(T--){
memset(hd,0,sizeof(hd));cnt=1;
scanf("%d%d",&n,&m);
s=id(n,m,P)+1;t=s+1;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
scanf("%d",&a[i][j][0]);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++){
scanf("%d",&v[i][j]);
for(k=1;k<P;k++)a[i][j][k]=a[i][j][k-1]/2;
add(s,id(i,j,0),inf);
add(id(i,j,P),t,inf);
if((i+j)&1)for(k=0;k<P;k++)add(id(i,j,k),id(i,j,k+1),k*v[i][j]);
else for(k=0;k<P;k++)add(id(i,j,k),id(i,j,k+1),(P-k-1)*v[i][j]);
}
int x1,x2,y1,y2,x;
scanf("%d",&q);
while(q--){
scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&x);
if((x2+y2)&1)swap(x1,x2),swap(y1,y2);
for(i=0;i<P;i++){
for(j=P-1;j>=0;j--)if(a[x1][y1][i]+a[x2][y2][j]>x)break;
if(j>=0)add(id(x2,y2,P-1-j),id(x1,y1,i+1),inf);
}
}
scanf("%d",&q);
while(q--){
scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&x);
if((x2+y2)&1)swap(x1,x2),swap(y1,y2);
for(i=0;i<P;i++){
for(j=0;j<P;j++)if(a[x1][y1][j]+a[x2][y2][i]<x)break;
if(j!=P)add(id(x1,y1,j),id(x2,y2,P-i),inf);
}
}
ll fl=dinic();
if(fl>=1e8)printf("impossible\n");
else printf("%lld\n",fl);
}
return 0;
}
J
题目描述
有$n$个初始为$1$的数，每次操作将一个区间的数统统乘以$2$或$3$，问$m$次操作后所有数$\gcd$是多少。
解题思路
solved by nikkukun
用差分维护一下每个点的$2,3$因子个数，取个$min$即可。
AC代码 - by nikkukun
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
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> pint;
const int N = 1e5 + 5;
const int MOD = 998244353;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
ll s2[N], s3[N];
void Solve(){
int n, q;
scanf("%d%d", &n, &q);
for(int i=1; i<=n; i++)
s2[i] = s3[i] = 0;
for(int i=1; i<=q; i++){
int l, r, x;
scanf("%d%d%d", &l, &r, &x);
if(x == 2) s2[l]++, s2[r+1]--;
else s3[l]++, s3[r+1]--;
}
ll mn2 = INF_LL, mn3 = INF_LL;
for(int i=1; i<=n; i++){
s2[i] += s2[i-1];
s3[i] += s3[i-1];
mn2 = min(mn2, s2[i]);
mn3 = min(mn3, s3[i]);
}
ll ans = 1;
for(int i=1; i<=mn2; i++)
ans = ans * 2LL % MOD;
for(int i=1; i<=mn3; i++)
ans = ans * 3LL % MOD;
printf("%lld\n", ans);
}
int main(){
int t; scanf("%d", &t);
while(t--) Solve();
return 0;
}
K
题目描述
给两个数组$a,b$，令$s(t)=\sum_{i=1}^n\lfloor\frac{t-b_i}{a_i}\rfloor$，有三种操作：
- $a_x=y$
- $b_x=y$
- 求最小的$t$满足$s(t)\geq k$
第三种操作数和$a_i$都在$1000$以内。
解题思路
solved by qxforever
用$bit[a_i]$维护$b_i\text{ mod }a_i$。
询问的时候二分答案，对于每一个分母作询问即可。
AC代码 - by qxforever
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
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e3+23;
const int mod = 998244353;
const int N = 1e5+23;
int n,m,T,k;
int a[N],b[N];
int bit[maxn][maxn],cnt[maxn];
ll ans;
inline int lowbit(int x)
{
return x&(-x);
}
void modify(int i,int x,int idx)
{
i++;
for(;i<=1000;i+=lowbit(i)) bit[idx][i]+=x;
}
int query(int i,int idx)
{
i++;
int ans=0;
for(;i;i-=lowbit(i)) ans+=bit[idx][i];
return ans;
}
bool check(ll t)
{
ll tmp=ans;
for(int i=1;i<=1000;i++){
tmp+=cnt[i]*(t/i);
int d=t%i;
//printf("%lld ",tmp);
tmp-=cnt[i]-query(d,i);
//printf("%lld\n",tmp);
if(tmp>=k+100000) return true;
}
//printf("t : %lld tmp : %lld\n",t,tmp);
return tmp>=k;
}
void read(int &x)
{
int f=1;x=0;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
x*=f;
}
int main()
{
//freopen("in.txt","r",stdin);
cin>>T;
while(T--){
memset(bit,0,sizeof(bit));memset(cnt,0,sizeof(cnt));
scanf("%d%d",&n,&m);
ans=0;
for(int i=1;i<=n;i++) read(a[i]);
for(int i=1;i<=n;i++) read(b[i]);
for(int i=1;i<=n;i++){
cnt[a[i]]++;
ans-=b[i]/a[i];
modify(b[i]%a[i],1,a[i]);
}
//cout<<query(0,6);
//cout<<ans<<endl;
//return 0*check(19);
while(m--){
int op;scanf("%d",&op);
if(op==3){
scanf("%d",&k);
ll L=0,R=1e13;
while(R-L>1){
ll mid=(L+R)>>1;
//printf("mid : %lld %d\n",mid,1*check(mid));
if(check(mid)) R=mid;
else L=mid;
}
printf("%lld\n",R);
}
else{
int x,y;scanf("%d%d",&x,&y);
ans+=b[x]/a[x];
modify(b[x]%a[x],-1,a[x]);
if(op==1){
cnt[a[x]]--;
a[x]=y;
ans-=b[x]/a[x];
modify(b[x]%a[x],1,a[x]);
cnt[a[x]]++;
}
else{
b[x]=y;
ans-=b[x]/a[x];
modify(b[x]%a[x],1,a[x]);
}
}
}
}
}
L
题目描述
给定$n$，求$\sum_{i=1}^{n}n\text{ mod }i$。
解题思路
$n\text{ mod }i=n-\lfloor\frac ni\rfloor*i$
对$i$分块，设$i\in[l,r]$时$\lfloor\frac ni\rfloor=p$，则这段区间第$j$位的贡献为
$\sum_{i=l}^{r}\frac {n-pi}{2^j}=\sum_{i=0}^{r-l}\frac{n+pi-pr}{2^j}$
其中，$n-pr=n\text{ mod }r$，故问题转化成了类欧几里得算法，再小范围暴力运算优化一下常数即可。
AC代码
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
typedef long long ll;
using namespace std;
ll f(ll a,ll b,ll c,ll n){
ll m=(a*n+b)/c;
if(!m||!a)return 0;
if(a>=c||b>=c)return (n*(n+1)/2*(a/c)+(b/c)*(n+1)+f(a%c,b%c,c,n));
else return m*n-f(c,c-b-1,a,m-1);
}
int main(){
ll i,j,k;
int t;
scanf("%d",&t);
while(t--){
ll n,ans=0;
scanf("%lld",&n);
// for(i=1;i<=min(n,10000000LL);i++)ans^=(n%i);
for(i = 1;i<=n;i=j+1){
j=n/(n/i);
if(j - i >= 1000){
for(k=0;k<40;k++)ans^=((f((n/i),n%j,1LL<<k,j-i))&1LL)<<k;
}else{
for(ll p = i; p <= j; p++)
ans ^= n % p;
}
}
printf("%lld\n",ans);
}
return 0;
}