签到：
A、D
铜牌题：
F
银牌：
J、K

A - Krypton

思路：
题目会有一个误区，很容易让人去想贪心（毕竟首充大的，奖励大嘛
有一种情况就是，我如果拿了尽可能大的，就没钱去买小的了，但是如果把小的全买了，奖励是更多的。
所以就枚举所有情况，二进制枚举，买哪些喽；

#include<bits/stdc++.h>
using namespace std;
#define ll long longint s[]={1,6,28,88,198,328,648};
int a[]={8,18,28,58,128,198,388};
int main(){int n;cin>>n;int ans=0;for(int i=0;i<(1<<7);i++){int res=0,cnt=0;for(int j=0;j<7;j++){if(i&(1<<j)){res+=s[j];cnt+=a[j];}}if(res<=n)ans=max(ans,cnt);}ans+=n*10;cout<<ans<<endl;return 0;
}

D - Meaningless Sequence

思路：
可以发现，$ai$ 的二进制数中有多少个 $1$ ，$ai$ 的权值就是 $c$的几次幂。
那么题目就变成了，小于等于 $n$，统计出现 不同的 $1$ 的出现次数，有几种可能。
考虑把 $n$ 的 二进制 中的一个 1 拆下来，那么剩下的位数就可以随便选，用一点点排列组合的小技巧就好啦；

ps: decimal 也有十进制的意思，查词典出来一个 小数制，呆滞了好久。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=1e9+7;ll qp(ll x,ll n){ll ans=1;while(n){if(n&1)ans=ans*x%mod;x=x*x%mod;n/=2;}return ans;
}char s[3050];
ll x;
ll cnt[30050];
ll jie[30050];
ll C(ll n,ll m){if(n<m)return 0;else return jie[n]*qp(jie[m],mod-2)%mod*qp(jie[n-m],mod-2)%mod;
}
int main(){scanf("%s%lld",s,&x);jie[0]=1;for(int i=1;i<=3000;i++)jie[i]=jie[i-1]*i%mod;int len=strlen(s);int res=0;for(int i=0;i<len;i++){if(s[i]=='1'){for(int j=1;i+j<len;j++){cnt[res+j]=(cnt[res+j]+C(len-i-1,j))%mod;}res++;cnt[res]=(cnt[res]+1)%mod;}}ll ans=1;for(int i=1;i<=3000;i++){ans=(ans+cnt[i]*qp(x,i)%mod)%mod;}cout<<ans<<endl;return 0;
}

F - Strange Memory

思路：
dsu on tree 的模板题吧。
考虑第一个问题，统计一棵树中，有多少对点满足，$ai$ $⨁$$aj$ = $a$ _$lca$；
这个工作就交给 dsu就好啦，众所周知，dsu 能够维护一颗子树的信息，而且对于没颗子树，都有一个插入轻子树的操作，这个时候我们就可以动态维护答案。
再来考虑 如何计算 下标异或和的问题，我们对于每个权值，存下标的二进制，也就是拆位啦，分别按位计算权值，但是记得给高位的 0，加权值（因为这个wa 了好几发）
因为空间可能会不够，我开了个哈希表映射了一下。

#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
#define ll long long
const ll mod=1e9+7;int n;
int col[100005];
vector<int>v[100005];
int siz[100005],son[100005];
ll ans=0;
int cnt[100022][22][2];
unordered_map<int,int>mp;
int tot=0;
ll cost[20];
void dfs(int x,int pre){siz[x]=1;for(auto to:v[x]){if(to==pre)continue;dfs(to,x);siz[x]+=siz[to];if(siz[son[x]]<siz[to])son[x]=to;}
}void del(int x,int pre){int p=x;for(int i=0;i<20;i++){cnt[mp[col[x]]][i][p%2]--;p/=2;}for(auto to:v[x])if(to!=pre)del(to,x);
}void add1(int x,int pre,int w){int p=x;if(mp.count(w^col[x])){int id=mp[w^col[x]];for(int i=0;i<20;i++){ans+=1LL*cnt[id][i][(p%2)^1]*cost[i];p/=2;}}for(auto to:v[x])if(to!=pre)add1(to,x,w);
}void add(int x,int pre){int p=x;for(int i=0;i<20;i++){cnt[mp[col[x]]][i][p%2]++;p/=2;}for(auto to:v[x])if(to!=pre)add(to,x);
}void add(int x){int p=x;for(int i=0;i<20;i++){cnt[mp[col[x]]][i][p%2]++;p/=2;}
}
void dsu(int x,int pre){for(auto to: v[x]){if(to==son[x]||to==pre)continue;dsu(to,x);del(to,x);}if(son[x])dsu(son[x],x);for(auto to:v[x])if(son[x]!=to&&to!=pre){add1(to,x,col[x]);add(to,x);}add(x);
}
int main(){scanf("%d",&n);cost[0]=1;for(int i=1;i<20;i++)cost[i]=cost[i-1]*2;for(int i=1;i<=n;i++){scanf("%d",&col[i]);if(!mp.count(col[i])){tot++;mp[col[i]]=tot;}}for(int i=1;i<n;i++){int a,b;scanf("%d%d",&a,&b);v[a].push_back(b);v[b].push_back(a);}dfs(1,0);dsu(1,0);printf("%lld\n",ans);return 0;
}

K - Ragdoll

思路：
对于 两个数的$gcd$ 等于两数的异或，想不到什么有用的性质；
但是一个数的 $gcd$ 只有可能是 它的因子，这样我们就能通过枚举一个数的因子，再去验证有没有一个数符合，然后存下来。
已知枚举因子是 调和级数的，时间复杂度$O(nlnn)$ 的，对于合并操作我们就启发式合并即可，剩下的就是按题意模拟。

ps:
注意 unordered_map 不要越界;

#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
#define ll long long
const ll mod=1e9+7;int n,m;
int col[300050];
int fa[300050];
int siz[300050];
unordered_map<int,int>mp[300050];vector<int>v[200050];void init(){for(int i=1;i<=200000;i++){for(int j=i;j<=200000;j+=i){if(__gcd(i,i^j)==i)v[j].push_back(i^j);}}
}
ll ans=0;
int find(int x){if(x==fa[x])return x;else return fa[x]=find(fa[x]);
}
void merge(int x,int y){int rt1=find(x);int rt2=find(y);if(rt1==rt2)return;if(siz[rt1]>siz[rt2])swap(rt1,rt2);fa[rt1]=rt2;for(auto to:mp[rt1]){for(auto k:v[to.first]){if(mp[rt2].find(k)!=mp[rt2].end())ans+=1LL*mp[rt2][k]*to.second;}}for(auto to:mp[rt1]){mp[rt2][to.first]+=to.second;}mp[rt1].clear();siz[rt2]+=siz[rt1];
}
int main(){init();scanf("%d%d",&n,&m);for(int i=1;i<=n+m;i++)fa[i]=i,siz[i]=1;for(int i=1;i<=n;i++){scanf("%d",&col[i]);mp[i][col[i]]++;}for(int i=1;i<=m;i++){int op,a,b;scanf("%d%d%d",&op,&a,&b);if(op==1){col[a]=b;mp[a][b]++;}else if(op==2){merge(a,b);}else{int rt=find(a);for(auto q:v[col[a]]){if(mp[rt].find(q)!=mp[rt].end())ans-=mp[rt][q];}mp[rt][col[a]]--;col[a]=b;mp[rt][col[a]]++;for(auto q:v[col[a]]){if(mp[rt].find(q)!=mp[rt].end())ans+=mp[rt][q];}}printf("%lld\n",ans);}return 0;
}

J - Abstract Painting

思路：
线性DP + 状压转移；
可以想到，如果我们用区间DP 转移会很丝滑，但是复杂度不够。
我们考虑到，对于一个圆，最多只会影响后面的 10 个位置，那么我们就可以用 状压DP来记录前面的10位，以此来进行转移；
考虑设置这样的DP状态，$DP[i][j]$，表示以 $i$ 为右边界，$j$是状压的二进制 的方案数，（二进制位上如果是1，代表这个点被圆覆盖了，如果是0，代表没被覆盖）。
我们可以 $2^5$ 枚举加圆的情况，用 $pos[i]$表示这种加圆情况，1代表作为圆左边界，$mask[i]$代表这种加圆方案对二进制的影响，即加圆的状态中，最大的圆会把内部都覆盖。
转移的话，也要对照设置的DP状态。
如果下一位会作为给定圆的右边界，那么当前位就一定会被覆盖，不能直接填空白地转移。
同理，如果下一位作为给定圆的右边界，那么给定圆的左边界一定不能是被覆盖的，并且加圆方案和状态要是合法的，即加圆的左边界要是不被覆盖的，等价于 两个二进制状态 & 起来是 0；
最后求个和即可。

ps:
这道题需要想到便于转移的状态，然后转移的话，就严格按照状态来转移即可。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=1e9+7;int n,k;
ll dp[1040][1050];
int pos[40],mask[40];
vector<int>v[1050];
int main(){scanf("%d%d",&n,&k);for(int i=1;i<=k;i++){int r,c;scanf("%d%d",&c,&r);c++;v[c+r].push_back(2*r);}for(int i=1;i<=31;i++){int tmp=0;for(int j=4;j>=0;j--){tmp=(tmp*2+((i>>j)&1))*2;if(!mask[i]&&((i>>j)&1))mask[i]=(1<<(2*j+1))-1;}pos[i]=tmp;}dp[0][1023]=1;ll ans=0;for(int i=0;i<=n;i++){for(int j=0;j<=1023;j++){if(v[i+1].size()==0){dp[i+1][(j<<1)%1024]+=dp[i][j];dp[i+1][(j<<1)%1024]%=mod;}for(int k=1;k<=31;k++){int f=0;for(auto to:v[i+1]){if(!((pos[k]>>(to-1))&1))f=1;if(f)break;}if(f||(j&pos[k]))continue;dp[i+1][((j|mask[k])<<1)%1024]+=dp[i][j];dp[i+1][((j|mask[k])<<1)%1024]%=mod;}}}for(int i=0;i<=1023;i++){ans+=dp[n+1][i];ans%=mod;}printf("%lld\n",ans);return 0;
}