by SJTU

B[J]

D[G]

判断从$1-n$长度的线段中抽取x个使得剩下任意三个都不能组成三角形

暴力

先预处理出子集中可以构成三角形的方案,然后再暴力枚举

复杂度$O(3^n + T2^n)$

F[G]

定义$\sum_{i=1}^{n-1} gcd(p_i,p_{i+1})$为一个排列p的值
对于n的所有排列,求其第值严格第k小的排列(任意输出一个)
$2k \leq n$

构造

注意条件$2k \leq n$

很明显排列$1,2,\dots,n$为最小的排列之一
考虑将其值 +k
若k为偶数,则直接将k移到2k前面
若k为奇数,将k移到2k前面,再将1移到原来k的位置

H[J]

I

主席树

J[G]

将一个数($10^{1000}$),拆成若干回文数的和(最多50个)

构造

每次减去比之小的最大的回文数,需要实现一个大数减法

K

考虑树状数组的区间更新操作
对于$[L,R]$,更新操作为add(R,1)add(L-1,-1)
最后树状数组中不为0的数为它们的cost
求区间 $[1,n]$ 中所有 $[L,R]$ 的cost和

二进制数位dp

$cnt_i$表示i二进制中1的个数,
$lcp(i,j)$表示(i,j)二进制的最长公共前缀(短的长度不足向前补0)
首先根据树状数组的原理,答案即为
$\sum_{i=1}^n \sum_{j=1}^n cnt_i + cnt_j - cnt_{lcp(i,j)}$

考虑逐位计算贡献

$\sum_{i=1}^n \sum_{j=1}^n cnt_i + cnt_j$

即1-n中所有数二进制中1的个数*n(每个数作为r出现n次),这个用组合数很容易统计

1
2
3
4
5
6
7
8
9
10
11
12
LL res = 0;
int cnt = 0;
for(int i=len-1;i>=0;--i)
{
if(bit[i])
{
F(j,cnt == 0,i)
res = (res + (j+cnt)*C[i][j]%mod) %mod;
++cnt;
}
}
res = (res+cnt)%mod;

$\sum_{i=1}^n \sum_{j=1}^n cnt_{lcp(i,j)}$

定义$P[i][j]$为长度为i的两串,最长公共前缀中1的个数为j的方案数

考虑前j个中取k个1,第$j+1$位不同(*2),j+1位以后任取

1
2
3
4
5
6
7
8
F(i,1,65) p2[i] = p2[i-1]*2%mod;
F(i,1,65)
{
P[i][0] = 2*p2[i-1]%mod*p2[i-1]%mod;
F(j,1,i-1)
F(k,0,j)
P[i][k] = (P[i][k] + C[j][k]*2%mod*p2[i-j-1]%mod*p2[i-j-1]%mod)%mod;
}

最后计算过程如下,分别考虑两串当前位为 0/1 1/0 0/0

1
2
3
4
5
6
7
8
9
10
11
12
13
LL res = 0;
int cnt = 0;
for(int i=len-1;i>=0;--i)
{
if(bit[i])
{
n -= 1LL << i;
res = (res + (n+1)%mod*p2[i]%mod*2*cnt%mod)%mod; // 0/1 1/0
F(j,0,i-1)
res = (res + (cnt+j)*P[i][j]%mod)%mod; // 0/0
++cnt;
}
}