100+35+10+10 拿下 rk7，拓扑AC的A题也太过困难了吧……
T1
题意
给定数组 \(a\)，数组长度为 \(n\)。
定义 \(f(x)\) 表示有多少对 \((i,j)\) 满足 \((a_i+x)\) 是 \((a_j+x)\) 的子集。
给定 \(k\)，保证 \(a_i<2^k\)，求 \(\sum_{i=0}^{2^{k-1}}f(i)\)。
\(n\leq20000,k\leq 60\)。
赛时思路
想对这个玩意进行转化。
首先转化成了位运算形式，即 \((a_i+x)|(a_j+x)==a_j+x\)。
然后就可以枚举 \(i,j,k\) 了，能拿 \(15pts\)。
现在又两条路走：要么对于每个 \(f(x)\) 单独考虑，要么考虑每对 \((i,j)\) 对答案的贡献。
一般这种题第二条路都更像是正解。
然后要进行进一步转化，我就不会了。
急急急！打完 \(O(n^2 2^k)\) 后罚坐至比赛开始两个多小时。
看看每两个数之间的贡献是否有什么规律吧。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1000;
int n,k,num[N][N],a[N],ans;
signed main(){
#ifndef ONLINE_JUDGE
freopen("in.in","r",stdin);
freopen("out.out","w",stdout);
#endif
ios::sync_with_stdio(0);
k=3;
n=1<<k;
for(int i=1;i<=n;i++){
a[i]=i-1;
}
for(int i=0;i<(1<<k);i++){
for(int j=1;j<=n;j++){
for(int l=1;l<=n;l++){
if(((a[j]+i)|(a[l]+i))==a[l]+i){
num[j][l]++;
ans++;
}
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cout<<num[i][j]<<' ';
}
cout<<'\n';
}
cout<<ans<<'\n';
}
先打出来 \(k=3\) 时每个数对的贡献看看。
输出：
8 4 4 2 4 2 2 1
0 8 4 4 2 4 2 2
0 0 8 4 4 2 4 2
0 0 0 8 4 4 2 4
0 0 0 0 8 4 4 2
0 0 0 0 0 8 4 4
0 0 0 0 0 0 8 4
0 0 0 0 0 0 0 8
嗯？怎么都是 \(2\) 的幂次？
再大一点呢？
16 8 8 4 8 4 4 2 8 4 4 2 4 2 2 1
0 16 8 8 4 8 4 4 2 8 4 4 2 4 2 2
0 0 16 8 8 4 8 4 4 2 8 4 4 2 4 2
0 0 0 16 8 8 4 8 4 4 2 8 4 4 2 4
0 0 0 0 16 8 8 4 8 4 4 2 8 4 4 2
0 0 0 0 0 16 8 8 4 8 4 4 2 8 4 4
0 0 0 0 0 0 16 8 8 4 8 4 4 2 8 4
0 0 0 0 0 0 0 16 8 8 4 8 4 4 2 8
0 0 0 0 0 0 0 0 16 8 8 4 8 4 4 2
0 0 0 0 0 0 0 0 0 16 8 8 4 8 4 4
0 0 0 0 0 0 0 0 0 0 16 8 8 4 8 4
0 0 0 0 0 0 0 0 0 0 0 16 8 8 4 8
0 0 0 0 0 0 0 0 0 0 0 0 16 8 8 4
0 0 0 0 0 0 0 0 0 0 0 0 0 16 8 8
0 0 0 0 0 0 0 0 0 0 0 0 0 0 16 8
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 16
还是对的！并且对角线上数一样！
这就意味着我们只需要得到第一行就可以算任意位置的贡献了！
对第一行取个 \(\log\) 看看呢？
k=4: 4 3 3 2 3 2 2 1 3 2 2 1 2 1 1 0
k=5: 5 4 4 3 4 3 3 2 4 3 3 2 3 2 2 1 4 3 3 2 3 2 2 1 3 2 2 1 2 1 1 0
k=6: 6 5 5 4 5 4 4 3 5 4 4 3 4 3 3 2 5 4 4 3 4 3 3 2 4 3 3 2 3 2 2 1 5 4 4 3 4 3 3 2 4 3 3 2 3 2 2 1 4 3 3 2 3 2 2 1 3 2 2 1 2 1 1 0
k=7: 7 6 6 5 6 5 5 4 6 5 5 4 5 4 4 3 6 5 5 4 5 4 4 3 5 4 4 3 4 3 3 2 6 5 5 4 5 4 4 3 5 4 4 3 4 3 3 2 5 4 4 3 4 3 3 2 4 3 3 2 3 2 2 1 6 5 5 4 5 4 4 3 5 4 4 3 4 3 3 2 5 4 4 3 4 3 3 2 4 3 3 2 3 2 2 1 5 4 4 3 4 3 3 2 4 3 3 2 3 2 2 1 4 3 3 2 3 2 2 1 3 2 2 1 2 1 1 0
好像非常有规律啊。
首先 \(k-1\) 的表是 \(k\) 的表的后缀。
然后从后往前4位4位地考虑，发现每4位都是形如：\(a+2,a+1,a+1,a\) 的。
从 \(2 1 1 0\) 开始，每次变换就是把每个数当成 \(a\) 后变成四个数。
答案就是变换的后缀。
但是这样都能考虑了，为什么不2位2位考虑呢？
然后再看了一会，发现这玩意其实就是相应下标的 \(popcount\)！
\(popcount(0)=0\)
\(popcount(1)=1\)
\(popcount(2)=1\)
\(popcount(3)=2\)
……
然后就会了，\(O(n^2)\) 枚举后把规律糊上去就行了。
后来又被 1ll<<k 和 __builtin_popcountll 硬控了半个小时。
#include<bits/stdc++.h>
#define W "w"
#define int long long
using namespace std;
const int N=2e5+10,mod=998244353;
int n,k,a[N],ans,pw[100];
signed main(){
freopen("subset.in","r",stdin);
freopen("subset.out",W,stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>k;
pw[0]=1;
for(int i=1;i<=k;i++) pw[i]=pw[i-1]*2%mod;
for(int i=1;i<=n;i++) cin>>a[i];
int all=(1ll<<k);
for(int i=1;i<=n;i++) a[i]++;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(a[i]>a[j]) continue;
int now=all-a[j]+a[i]-1;
(ans+=pw[__builtin_popcountll(now)])%=mod;
}
}
cout<<ans<<'\n';
}
T2
题意
给定数组 \(a\)，长度为 \(n\)。
将 \(a_i\) 变成 \(x\) 需要付出 \(|a_i-x|\) 的代价。
求将 \(a\) 中每个数都变成 \(d\) 的幂次的最小代价。
\(d\) 可任选。
设 \(V=max(a_i)\)
\(n\leq 100000,1\leq V\leq 10^{12}\)
赛时思路
如果 \(d\) 固定的话，我会 \(O(n)\)。
所以问题在于确定 \(d\)。
二分？这玩意好像没啥单调性。
根号分治！
对于 \(d\leq\sqrt V\) ，可以枚举 \(d\)，能做到 \(O(n\sqrt V)\)。
（实际上可以更优，但是我场上没想到，所以一直觉得根号分治不是正解。
对于 \(d>\sqrt V\)，我不会！
于是将 \(d\) 枚举到 600 后跑路，拿了 \(35pts\)。
T3
打了 \(10pts\) 爆搜。
T4
输出了 \(0.5000000000\)，获得 \(10pts\)。
正解会补的（大概会？）
标签：AC,NOIP,16,int,拓扑,long,leq,popcount,freopen From： https://www.cnblogs.com/hugoi/p/18538999