Codeforces Round 499 (Div. 1)

发表于 更新于 分类于

https://codeforces.com/contest/1010

A. Fly

二分答案，送分题。

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
#include<bits/stdc++.h>
using namespace std;

void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
 
void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}

#define lf double
#define ll long long 

#define pii pair<int,int >
#define vec vector<int >

#define pb push_back
#define mp make_pair
#define fr first
#define sc second

#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++) 

const int maxn = 2e5+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;

int a[maxn],b[maxn],n,m;

int check(lf x) {
    for(int i=1;i<=n-1;i++) {
        x-=(x+m)/(lf)a[i];
        x-=(x+m)/(lf)b[i+1];
        if(x<0) return 0;
    }x-=(x+m)/(lf)a[n];
    x-=(x+m)/(lf)b[1];
    if(x<0) return 0;
    return 1;
}

int main() {
    read(n),read(m);
    FOR(i,1,n) read(a[i]);
    FOR(i,1,n) read(b[i]);
    lf l=0,r=2e9;
    while(r-l>1e-6) {
        lf mid=(l+r)*0.5;
        if(check(mid)) r=mid;
        else l=mid;
    }
    if(l>1e9) puts("-1");
    else printf("%.10lf\n",l);
    return 0;
}

B. Rocket

简单的交互题。

第一轮先每次都问$1$，问出这个位置是真还是假，然后二分答案就好了。

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;

void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
 
void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}

#define lf double
#define ll long long 

#define pii pair<int,int >
#define vec vector<int >

#define pb push_back
#define mp make_pair
#define fr first
#define sc second

#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++) 

const int maxn = 2e5+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;

int a[maxn],n,m;

int main() {
    read(n),read(m);
    for(int i=1;i<=m;i++) {
        puts("1");fflush(stdout);
        read(a[i]);if(!a[i]) return 0;
    }
    int l=1,r=n;
    for(int i=m+1;i<=60;i++) {
        int mid=(l+r)>>1,x;
        write(mid);fflush(stdout);read(x);
        if(!x) return 0;
        if(x==a[(i-1)%m+1]) l=mid+1;
        else r=mid-1;
    }
    return 0;
}

C. Border

小凯的疑惑。

先把所有数求$\gcd$，那么这就是我们可以凑出来的最小的非$0$数了，具体参见小凯的疑惑，两个互质的数$a,b$不可以凑出来的最小的数是$ab-a-b$。

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
#include<bits/stdc++.h>
using namespace std;

void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
 
void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}

#define lf double
#define ll long long 

#define pii pair<int,int >
#define vec vector<int >

#define pb push_back
#define mp make_pair
#define fr first
#define sc second

#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++) 

const int maxn = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;

int a[maxn],n,m,c[maxn][2],f[maxn],g[maxn],op[maxn],vis[maxn];

int main() {
    read(n),read(m);int t=m;
    for(int i=1;i<=n;i++) read(a[i]),t=__gcd(t,a[i]);
    int x=t;
    while(!vis[x]) vis[x]=1,x=(x+t)%m;
    int ans=0;
    for(int i=0;i<m;i++) ans+=vis[i];write(ans);
    for(int i=0;i<m;i++) if(vis[i]) printf("%d ",i);puts("");
    return 0;
}

D. Mars rover

简单的$\rm tree\ dp$，设$f[i]$表示$i$的子树传上来的数，$g[i]$表示$i$这个点的结果反转，忽视$i$的子树，$1$的结果。

那么直接深搜暴力更新就好了，先更新$f$在更新$g$。

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
#include<bits/stdc++.h>
using namespace std;

void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
 
void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}

#define lf double
#define ll long long 

#define pii pair<int,int >
#define vec vector<int >

#define pb push_back
#define mp make_pair
#define fr first
#define sc second

#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++) 

const int maxn = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;

int a[maxn],n,m,c[maxn][2],f[maxn],g[maxn],op[maxn];

char s[5];

void dfs(int x) {
    if(c[x][0]) dfs(c[x][0]);
    if(c[x][1]) dfs(c[x][1]);
    int a=f[c[x][0]],b=f[c[x][1]];
    if(op[x]==1) f[x]=a&b;
    else if(op[x]==2) f[x]=a|b;
    else if(op[x]==3) f[x]=a^b;
    else if(op[x]==4) f[x]=!a;
}

void dp(int x,int fa,int e) {
    if(x!=1) {
        int o=op[fa];
        if(o==1) {
            if((f[e]&(!f[x]))!=f[fa]) g[x]=g[fa];
            else g[x]=f[1];
        } else if(o==2) {
            if((f[e]|(!f[x]))!=f[fa]) g[x]=g[fa];
            else g[x]=f[1];
        } else if(o==3) {
            if((f[e]^(!f[x]))!=f[fa]) g[x]=g[fa];
            else g[x]=f[1];
        } else if(o==4) g[x]=g[fa];
    }
    if(c[x][0]) dp(c[x][0],x,c[x][1]);
    if(c[x][1]) dp(c[x][1],x,c[x][0]);
}

int main() {
    read(n);
    for(int i=1;i<=n;i++) {
        scanf("%s",s+1);
        if(s[1]=='A') op[i]=1;
        else if(s[1]=='O') op[i]=2;
        else if(s[1]=='X') op[i]=3;
        else if(s[1]=='N') op[i]=4;
        else op[i]=5;
        if(op[i]<=3) read(c[i][0]),read(c[i][1]);
        else if(op[i]==4) read(c[i][0]);
        else read(f[i]);
    }
    dfs(1);
    g[1]=!f[1];
    dp(1,0,0);
    for(int i=1;i<=n;i++) if(op[i]==5) putchar(g[i]+'0');
    return 0;
}

E. Store

$\rm kd\ tree$，不想写先咕着…

F. Tree

这是一道毒瘤题。

设$v_i$表示第$i$个点的果子数，设$b_i=v_i-\sum_{x\in son}v_x$，显然依题意要满足$b_i\geqslant 0$。

根据差分的性质我们可以得到$\sum b_i=x$。

假设我们硬点树上剩下了$m$个点，则根据插板法$b_i$的方案数为$\displaystyle\binom{x+m-1}{m-1}$。

由于$b$唯一确定$v$，所以$v$的方案数也是这么多。

那么我们就考虑剩下$m$个点的方案数。

考虑一种暴力的$dp$，设$f[u][i]$表示$x$子树保留了$i$个点(包括$i$)的方案数，转移显然：

写成生成函数就是：

若$u$只有一个儿子也同理：

若$u$为叶子则：

证明显然。

考虑这个玩意怎么优化，显然如果$\rm NTT$优化复杂度$O(n^2\log n)$，这是我们无法接受的。

我们考虑对这棵树进行轻重链剖分，那么对于一条重链上的每个点我们假设求出了非重儿子的$F(x)$。

那么我们对这条重链进行编号，从顶端到叶子为$1\cdots c$，设$a_i=xF_{son_i}(x)$。

那么链顶的答案就是：

我们递归的写完所有$c$个：

暴力展开就是：

这个可以分治$\rm FFT$解决，代码大概长这样：

1
2
3
4
5
void solve(int lt,int rt,vec &a,vec &b) {
    if(lt==rt) return a=b=r[lt],void();
    vec al,ar,bl,br;int mid=(lt+rt)>>1;solve(lt,mid,al,bl),solve(mid+1,rt,ar,br);
    b=poly::pmul(bl,br);a=poly::padd(poly::pmul(ar,bl),al);
}

其中$al,ar$表示答案，$bl,br$表示区间乘积，其他的变量可以参考下下面的代码。

那么我们就解决了这个问题，因为总轻边的子树大小之和为$O(n\log n)$，所以总复杂度为$O(n\log ^3n)$。

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
122
123
124
125
126
127
128
129
130
#include<bits/stdc++.h>
using namespace std;

void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
 
void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}

#define lf double
#define ll long long 

#define pii pair<int,int >
#define vec vector<int >

#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define _sz(x) ((int)x.size())

#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++) 

const int maxn = 1<<19|10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 998244353;

int add(int x,int y) {return x+y>=mod?x+y-mod:x+y;}
int del(int x,int y) {return x-y<0?x-y+mod:x-y;}
int mul(int x,int y) {return 1ll*x*y-1ll*x*y/mod*mod;}

int qpow(int a,int x) {
    int res=1;
    for(;x;x>>=1,a=mul(a,a)) if(x&1) res=mul(res,a);
    return res;
}

namespace poly {
    int N,w[maxn],pos[maxn],bit,mxn,t[2][maxn];

    void init(int l) {
        for(mxn=1;mxn<=l;mxn<<=1) ;
        w[0]=1,w[1]=qpow(3,(mod-1)/mxn);
        for(int i=2;i<=mxn;i++) w[i]=mul(w[i-1],w[1]);
    }

    void ntt(int *r,int op) {
        FOR(i,1,N-1) if(pos[i]>i) swap(r[pos[i]],r[i]);
        for(int i=1,d=mxn>>1;i<N;i<<=1,d>>=1)
            for(int j=0;j<N;j+=i<<1)
                for(int k=0;k<i;k++) {
                    int x=r[j+k],y=mul(r[i+j+k],w[k*d]);
                    r[j+k]=add(x,y),r[i+j+k]=del(x,y);
                }
        if(op==-1) {
            reverse(r+1,r+N);int d=qpow(N,mod-2);
            for(int i=0;i<N;i++) r[i]=mul(r[i],d);
        }
    }

    vec pmul(vec a,vec b) {
        if(1ll*_sz(a)*_sz(b)<=5000) {
            vec c;c.resize(_sz(a)+_sz(b)-1);
            FOR(i,0,_sz(a)-1) FOR(j,0,_sz(b)-1) c[i+j]=add(c[i+j],mul(a[i],b[j]));
            return c;
        }
        for(N=1,bit=0;N<_sz(a)+_sz(b);N<<=1,bit++);
        FOR(i,0,N-1) pos[i]=pos[i>>1]>>1|((i&1)<<(bit-1));
        FOR(i,0,_sz(a)-1) t[0][i]=a[i];FOR(i,_sz(a),N) t[0][i]=0;
        FOR(i,0,_sz(b)-1) t[1][i]=b[i];FOR(i,_sz(b),N) t[1][i]=0;
        ntt(t[0],1),ntt(t[1],1);
        FOR(i,0,N-1) t[0][i]=mul(t[0][i],t[1][i]);
        ntt(t[0],-1);vec c;
        FOR(i,0,_sz(a)+_sz(b)-1) c.pb(t[0][i]);
        return c;
    }

    vec padd(vec a,vec b) {
        if(_sz(a)>_sz(b)) {FOR(i,0,_sz(b)-1) a[i]=add(a[i],b[i]);return a;}
        FOR(i,0,_sz(a)-1) b[i]=add(a[i],b[i]);return b;
    }
}

ll k;
int n,ch[maxn],head[maxn],tot,sz[maxn],F[maxn],cnt;
struct edge{int to,nxt;}e[maxn<<1];

vec f[maxn],r[maxn];

void ins(int u,int v) {e[++tot]=(edge){v,head[u]},head[u]=tot;}

void dfs(int x,int fa) {
    sz[x]=1;F[x]=fa;
    for(int i=head[x],v;i;i=e[i].nxt)
        if((v=e[i].to)!=fa) {dfs(v,x);sz[x]+=sz[v];if(sz[ch[x]]<sz[v]) ch[x]=v;}
}

void solve(int lt,int rt,vec &a,vec &b) {
    if(lt==rt) return a=b=r[lt],void();
    vec al,ar,bl,br;int mid=(lt+rt)>>1;solve(lt,mid,al,bl),solve(mid+1,rt,ar,br);
    b=poly::pmul(bl,br);a=poly::padd(poly::pmul(ar,bl),al);
}

vec dfs2(int x) {
    for(int t=x;t;t=ch[t]) {
        for(int i=head[t];i;i=e[i].nxt) if(e[i].to!=F[t]&&e[i].to!=ch[t]) f[t]=dfs2(e[i].to);
        if(_sz(f[t])<1) f[t].resize(1);f[t][0]++;
        f[t].insert(f[t].begin(),0);
    }
    cnt=0;for(int t=x;t;t=ch[t]) r[++cnt]=f[t];
    vec a,b;solve(1,cnt,a,b);return a;
}

int main() {
    read(n),scanf("%lld",&k);poly::init(n<<1);k%=mod;
    for(int i=1,x,y;i<n;i++) read(x),read(y),ins(x,y),ins(y,x);
    dfs(1,0);vec res=dfs2(1);int t=1,ans=0;
    for(int i=1;i<_sz(res);i++) {
        ans=add(ans,mul(res[i],t));
        t=mul(t,mul((k+i)%mod,qpow(i,mod-2)));
    }write(ans);
    return 0;
}