BZOJ5480~5482题解

5480

很想点分治,但是不太会。这里有一个处理链并的优秀做法。

考虑所有包含(u,v)的路径(a,b),其中gcd(u,v)=u,dfn[a]<dfn[b]。

第一种情况

第二种情况

由于刚才打的题解没保存。。不想打了,就贴图贴pdf了。

5481

oeis好题,光速溜溜溜

70分可以dp或者二项式反演或者fft+exp,然而我不会。

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
#include <bits/stdc++.h>
using namespace std;
#define IL inline
IL int read() { int x; int _w = scanf("%d", &x); return x; }
IL int read(int &x) { int _w=scanf("%d", &x); }
IL void write(int x) { printf("%d\n", x); }
#define rep(i, j, k) for (int i = j; i <= k; ++i)
#define repd(i, j, k) for (int i = j; i >= k; --i)
#define pb push_back
#define mp make_pair
#define fr first
#define se second
#define ls (p<<1)
#define rs (p<<1|1)
#define ef else if
#define re real
#define im imag
#define fre(x) freopen(x".in","r",stdin),freopen(x".out", "w", stdout)
#define popcnt(x) __builtin_popcount(x)
#define ls (p<<1)
#define rs (p<<1|1)
#define cpx my_complex
#define ll long long
const int maxn = 1e7+10;
//a(n) = (1/2)*n*(n-1)^2*((2*n-3)*a(n-2)+(n-2)^2*a(n-3))
const int t=998244353;
const ll inv2=499122177;
#define p(x) ((x+=d)%=t)
int a,b,c,d,out;
IL ll sqr(ll x) {return x*x%t;}
int g[maxn],f[maxn];
int main() {
a=1,b=0,c=1,out=1;
int n=read();
if(n<=2){puts(n==1?"0":"1");return 0;}
rep(i,1,n)g[i]=1ll*i*i%t,f[i]=inv2*i%t;
int i=3;
for(;i+7<=n;i+=8)
d=1ll*f[i ]*g[i-1]%t*((1ll*(2*i-3)*b%t+1ll*g[i-2]*a%t)%t)%t,a=b,b=c,c=d,p(out),
d=1ll*f[i+1]*g[i ]%t*((1ll*(2*i-1)*b%t+1ll*g[i-1]*a%t)%t)%t,a=b,b=c,c=d,p(out),
d=1ll*f[i+2]*g[i+1]%t*((1ll*(2*i+1)*b%t+1ll*g[i-0]*a%t)%t)%t,a=b,b=c,c=d,p(out),
d=1ll*f[i+3]*g[i+2]%t*((1ll*(2*i+3)*b%t+1ll*g[i+1]*a%t)%t)%t,a=b,b=c,c=d,p(out),
d=1ll*f[i+4]*g[i+3]%t*((1ll*(2*i+5)*b%t+1ll*g[i+2]*a%t)%t)%t,a=b,b=c,c=d,p(out),
d=1ll*f[i+5]*g[i+4]%t*((1ll*(2*i+7)*b%t+1ll*g[i+3]*a%t)%t)%t,a=b,b=c,c=d,p(out),
d=1ll*f[i+6]*g[i+5]%t*((1ll*(2*i+9)*b%t+1ll*g[i+4]*a%t)%t)%t,a=b,b=c,c=d,p(out),
d=1ll*f[i+7]*g[i+6]%t*((1ll*(2*i+11)*b%t+1ll*g[i+5]*a%t)%t)%t,a=b,b=c,c=d,p(out);
for(;i<=n;++i)
d=1ll*f[i]*g[i-1]%t*((1ll*(2*i-3)*b%t+1ll*g[i-2]*a%t)%t)%t,a=b,b=c,c=d,p(out);
printf("%d",out);
return 0;
}

5482

把网上的边看成-1,向下看成加1,由于二叉树的深度是log,直接枚举对于p[i]的lca,然后dp求子树中还有容量的点的距离最小值,模拟费用流。

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
#include <bits/stdc++.h>
using namespace std;
#define IL inline
IL int read() { int x; int _w = scanf("%d", &x); return x; }
IL int read(int &x) { int _w=scanf("%d", &x); }
IL void write(int x) { printf("%d ", x); }
#define rep(i, j, k) for (int i = j; i <= k; ++i)
#define repd(i, j, k) for (int i = j; i >= k; --i)
#define pb push_back
#define mp make_pair
#define fr first
#define se second
#define ls (p<<1)
#define rs (p<<1|1)
#define ef else if
#define re real
#define im imag
#define fre(x) freopen(x".in","r",stdin),freopen(x".out", "w", stdout)
#define popcnt(x) __builtin_popcount(x)
#define ls (p<<1)
#define rs (p<<1|1)
#define cpx my_complex
#define ll long long
const int maxn=3e5+10;
const int INF=1e9;
int n,m;
int down[maxn],ch[maxn],flow[maxn],c[maxn];
IL void calc(int x){
ch[x]=2; int y;
down[x]=c[x]?0:INF;
rep(i,0,1)if((y=2*x+i)<=n){
int cur=down[y]+(flow[y]>=0?1:-1);
if(cur<down[x])down[x]=cur,ch[x]=i;
}
}
void find(int x){
if(ch[x]==2)c[x]--;
else {
int y=x*2+ch[x];
find(y);
flow[y]++;
}
calc(x);
}
int main(){
// freopen("1.in","r",stdin);
n=read();m=read();
rep (i,1,n)c[i]=read();
repd(i,n,1)calc(i);
int ans=0;
rep(i,1,m){
int x=0,p=0,minv=INF;
read(x);
for(int y=x,add=0;y;y>>=1){
if(down[y]+add<minv)minv=down[y]+add,p=y;
add+=flow[y]<=0?1:-1;
}
ans+=minv;
write(ans);
for(int y=x;y!=p;y>>=1)flow[y]--,calc(y);
find(p);
for(int y=p;y;y>>=1)calc(y);
}
return 0;
}
/*
5 4
0 0 4 1 1
2 4 5 2
*/