你最愿意做的哪件事，才是你的天赋所在

0%

2020CCPC长春站

发表于 Valine：

比赛过程

一来我们分开看题，从前到后，从后到前，然后我看中间的D题。

一看感觉可以做，先上去打了个表，然后发现规律了，这时候队友说A题是签到题可以写，然后我就让出了电脑，然后我把D题跟队友说一下后修正思路确认了，然后等A题过了我就上去写D题，最后F题队友说启发式暴力合并可以过，但是需要维护一个集合的异或和，最后想到只要按位拆分01的个数维护起来就可以了，然后两个半小时得时候就过了，最后还刻了JKL三道题，最后三个人决定一起写K，然后一开始思路绕进去了，最后队友说一开始的思路是错的，这时候只剩下一个半小时重新想了，然后发现K的对数不是很多，可以先$n \times \sqrt n$的复杂度先处理出来因子，然后找到对数之后启发式暴力合并就可以了。写完只剩下10分钟，最后乱交了几发也没过，很可惜，在情况3的时候，多跑了一个加法。赛后才找到。

A - 签到题

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
/*
队伍名称：三剑客
*/
#include <bits/stdc++.h>
using namespace std;
int n;
int vis[10000];
int a[8]={1,6,28,88,198,328,648};
int b[8]={8,18,28,58,128,198,388};
int ans=0;
void dfs(int sum,int as){
    if(sum==0){
        ans=max(ans,as);
        return;
    }
    bool flag=0;
    for(int i=0;i<7;i++){
        if(!vis[i]&&sum>=a[i]) {
            vis[i]=1;
            dfs(sum-a[i],as+a[i]*10+b[i]);
            vis[i]=0;
            flag=1;
        }
    }
    if(!flag){
        dfs(0,as+sum*10);
    }
}
int main(){
    cin>>n;
    dfs(n,0);
    cout<<ans<<endl;
    return 0;
}

D-规律题

打个表不难发现每个数的贡献$f(n)=C^{n拆成二进制数后1的个数}$,然后就是简单的组合问题，从低位向高位找1，每找到一个1，可以假设这一位是1的话，那么后面的数就随便选，如果这个数是0，那么就加上剩下的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
52
53
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
inline bool isprime(ll num)
{if(num==2||num==3)return true;
    if(num%6!=1&&num%6!=5)return false;
    for(int i=5;1ll*i*i<=num;i+=6){if(num%i==0||num%(i+2)==0)return false;}
    return true;}
const int mod = 1e9+7;
inline ll mul(ll a,ll b,ll c){return (a*b-(ll)((ld)a*b/c)*c+c)%c;}
inline ll exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=1;y=0;return a;}ll g = exgcd(b,a%b,y,x);y-=a/b*x;return g;}
inline ll quick_pow(ll a,ll b,ll mod){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll quick_pow(ll a,ll b){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll inv(ll x){return quick_pow(x,mod-2);}
inline ll inv(ll x,ll mod){return quick_pow(x,mod-2,mod);}
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
const int N =  3500;
ll fac[N];
ll Inv[N];
void init(){
    fac[0]=1;
    for(int i=1;i<N;i++){
        fac[i]=fac[i-1]*i%mod;
    }
    Inv[N-1]=inv(fac[N-1]);
    for(int i=N-2;i>=0;i--)Inv[i]=Inv[i+1]*(i+1)%mod;
}
ll C(int n,int m){
    if(n<m)return 0;
    return fac[n]*Inv[m]%mod*Inv[n-m]%mod;
}
int main(){
    string s;
    ll c;
    cin>>s>>c;
    init();
    ll ans = 1;
    reverse(s.begin(),s.end());
    int one = 0;
    for(int i=0;i<s.size();i++){
        if(s[i]=='1')one++;
    }
    for(int i=0;i<s.size();i++){
        if(s[i]=='1'){
            for(int j=0;j<=i;j++){
                ans=(ans+C(i,j)*quick_pow(c,j+one)%mod)%mod;
                if(j==0)one--;
            }
        }
    }
    printf("%lld\n",ans);
}

F - 暴力

队友过的题，题目都没看，不过貌似是DSU on tree

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
131
132
133
//
// Created by three_konjaks on 2020/11/8.
//

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<climits>
#include<stack>
#include<vector>
#include<queue>
#include<set>
#include<bitset>
#include<map>
//#include<regex>
#include<cstdio>
#include <iomanip>
#pragma GCC optimize(2)
#define up(i,a,b)  for(int i=a;i<b;i++)
#define dw(i,a,b)  for(int i=a;i>b;i--)
#define upd(i,a,b) for(int i=a;i<=b;i++)
#define dwd(i,a,b) for(int i=a;i>=b;i--)
//#define local
typedef long long ll;
typedef unsigned long long ull;
const double esp = 1e-6;
const double pi = acos(-1.0);
const int INF = 0x3f3f3f3f;
const int inf = 1e9;
using namespace std;
ll read()
{
char ch = getchar(); ll x = 0, f = 1;
while (ch<'0' || ch>'9') { if (ch == '-')f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
return x * f;
}
typedef pair<int, int> pir;
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define lrt root<<1
#define rrt root<<1|1
const int N=1e5+10;
const int M=1e6+10;
int n;
int a[N];
int dfn[N],son[N],sz[N],rk[N],d[N];
int st=0;
vector<int>vec[N];
void dfs1(int u,int fa,int dep){
    sz[u]=1;
    d[u]=dep;
    dfn[u]=++st;
    rk[st]=u;
    for(auto k:vec[u]) {
        if (k == fa)continue;
        dfs1(k, u, dep + 1);
        if (son[u] == -1 || sz[son[u]] < sz[k]) {
            son[u] = k;
        }
        sz[u] += sz[k];
    }
}
int cnt[M][40];
int cntval[M];
void add(ll val,ll x){
    cntval[val]++;
    up(i,0,30){
        if(x>>i&1)cnt[val][i]++;
    }
}
ll getans(ll val,ll t){
    ll res=0;
    up(i,0,30){
        if(t>>i&1){
            ll num=cntval[val]-cnt[val][i];
            res+=num*(1ll<<i);
        }
        else {
            ll num=cnt[val][i];
            res+=num*(1ll<<i);
        }
    }
    return res;
}
ll ans=0;
void dfs2(int u,int fa,bool is)
{
    for(auto k:vec[u]){
        if(k==fa||k==son[u])continue;
        dfs2(k,u,0);
    }
    if(son[u]!=-1)dfs2(son[u],u,1);
    for(auto k:vec[u]){
        if(k==fa||k==son[u])continue;
        up(i,dfn[k],dfn[k]+sz[k]){
            ll temp=a[rk[i]];
            ll tempxor=a[u]^temp;
            if(tempxor<M&&cntval[tempxor]){
                ans+=getans(tempxor,rk[i]);
            }
        }
        up(i,dfn[k],dfn[k]+sz[k]){
            add(a[rk[i]],rk[i]);
        }
    }
    add(a[u],u);
    if(!is){
        up(i,dfn[u],dfn[u]+sz[u]){
            up(j,0,30){
                cnt[a[rk[i]]][j]=0;
                cntval[a[rk[i]]]=0;
            }
        }
    }
}
int main(){
    memset(son,-1,sizeof(son));
    n=read();
    upd(i,1,n)a[i]=read();
    int u,v;
    upd(i,1,n-1){
        u=read(),v=read();
        vec[v].push_back(u);
        vec[u].push_back(v);
    }
    dfs1(1,0,0);
    dfs2(1,0,1);
    cout<<ans<<endl;
    return 0;
}

K-DSU on tree

这题步骤很多，首先筛去所有因子就不多解释了，说一下暴力合并的时候如何做，合并的数据结构当然是使用并查集了

首先是第一个操作，新加一个节点,直接给值列表复制，然后用vector来维护一棵树就好

然后是合并两棵树的操作，因为是启发式合并，所以要统计树的大小height，从小的向大的合并，可以证明整体复杂度是nlog的，

先用当前答案减去小树的答案，然后将小树的节点一个一个的插入到大的树上去就可以了。

然后是change操作，这个操作其实是第二个操作的子操作，相当于在这棵树上删除一个节点，然后在插入一个节点。

在维护每棵树的孩子的时候，需要用unordered_map，这样可以达到O（lg）的复杂度进行插入，这个log的来源是删除的值和插入的值的匹配个数（即先前预处理出来的值）。

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
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
//
// Created by three_konjaks on 2020/11/8.
//

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<climits>
#include<stack>
#include<vector>
#include<queue>
#include<set>
#include<bitset>
#include<map>
//#include<regex>
#include<cstdio>
#include <iomanip>
#include <unordered_map>
#pragma GCC optimize(2)
#define up(i,a,b)  for(int i=a;i<b;i++)
#define dw(i,a,b)  for(int i=a;i>b;i--)
#define upd(i,a,b) for(int i=a;i<=b;i++)
#define dwd(i,a,b) for(int i=a;i>=b;i--)
//#define local
typedef long long ll;
#define ld long double
typedef unsigned long long ull;
const double esp = 1e-6;
const double pi = acos(-1.0);
const int INF = 0x3f3f3f3f;
const int inf = 1e9;
using namespace std;
const int mod = 1e9+7;
inline ll mul(ll a,ll b,ll c){return (a*b-(ll)((ld)a*b/c)*c+c)%c;}
inline ll exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=1;y=0;return a;}ll g = exgcd(b,a%b,y,x);y-=a/b*x;return g;}
inline ll quick_pow(ll a,ll b,ll mod){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll quick_pow(ll a,ll b){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll inv(ll x){return quick_pow(x,mod-2);}
inline ll inv(ll x,ll mod){return quick_pow(x,mod-2,mod);}
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll read()
{
    char ch = getchar(); ll x = 0, f = 1;
    while (ch<'0' || ch>'9') { if (ch == '-')f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}
typedef pair<int, int> pir;
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define lrt root<<1
#define rrt root<<1|1
const int N=2e5+10;
ll n,m;
vector<ll>fac[N];
vector<ll>p[N];
ll cnt[N*2];
ll ans[2*N];
ll a[N*2];
vector<ll>vec[N*2];
vector<ll>son[N*2];
ll lastans=0;
unordered_map<ll,ll>unmap[N*2];
void insert(int rt,ll val){
    unmap[rt][val]++;
    for(auto k:p[val]){
        ans[rt]+=unmap[rt][k];
        lastans+=unmap[rt][k];
    }
}
struct bcj{
    int height[2*N];
    int par[2*N];
    void init() {
        upd(i, 0, 2 * N - 10)
        {
            par[i]=i;
            height[i]=1;
        }
    }
    int f(int x){
        return x==par[x]?x:par[x]=f(par[x]);
    }
    bool same(int i,int j){
        return f(i)==f(j);
    }
    bool merge(int x,int y){
        x=f(x);
        y=f(y);
        if(x==y)return 0;
        if(height[y]>height[x])
            swap(x,y);
        for(auto k:son[y]){
            son[x].push_back(k);
            insert(x,a[k]);
        }
        unmap[y].clear();
        par[y]=x;
        height[x]+=height[y];
        return 1;
    }
}B;
void init(){
    for(int i=2;i<N;i++){
        int m = sqrt(i);
        fac[i].push_back(1);
        for(int j=2;j<=m;j++){
            if(i%j==0){
                fac[i].push_back(j);
                if(1ll*j*j!=i)fac[i].push_back(i/j);
            }
        }
    }
}

int main(){
    n=read(),m=read();
    init();
    B.init();
    int x,y;
    upd(i,1,n){
        x=read();vec[i].push_back(x);
        son[i].push_back(i);
        unmap[i][x]++;
        a[i]=x;
    }
    for(int i=2;i<N;i++){
        int len = fac[i].size();
        for(int j=0;j<len;j++){
            int l = i^fac[i][j];
            if(gcd(i,l)==(i^l)){
                p[i].push_back(l);
            }
        }
    }
    int op;
    while(m--){
        op=read();
        if(op==2){
            x=read(),y=read();
            if(B.same(x,y)){
                printf("%lld\n",lastans);
                continue;
            }
            if(B.height[B.f(y)]>B.height[B.f(x)])swap(x,y);
            lastans-=ans[B.f(y)];
            ans[B.f(y)]=0;
            B.merge(x,y);
            printf("%lld\n",lastans);
        }
        else if(op==1){
            x=read(),y=read();
            a[x]=y;
            son[x].push_back(x);
            unmap[x][y]++;
            printf("%lld\n",lastans);
        }else {
            x=read(),y=read();
            int fa=B.f(x);
            for(auto k : p[a[x]]){
                lastans-=unmap[fa][k];
                ans[fa]-=unmap[fa][k];
            }
            unmap[fa][a[x]]--;
            insert(fa,y	);
            a[x]=y;
            printf("%lld\n",lastans);
        }
    }
    return 0;
};
-------------你最愿意做的哪件事才是你的天赋所在-------------