o.O ?
B
在 \(\{a_n\}\) 中选出若干数使得两两的乘积不为完全立方数。
\(n\le 10^5\)，\(1\le a_i\le 10^{10}\)，TL=1s.
如果其有一个 \(>10^5\) 的质因子一定对答案有贡献。
考虑其余的数，先令它们除去所有非 \(1\) 的完全立方因子。
若有多个 \(1\)，只有一个对答案有贡献。否则一个数对应着一个唯一的数，从两个里选择出现次数最大的那个。
ll Pollard_Rho(ll n){
if(!(n&1))return 2;
ll d,x,y,c;
while(true){
d=1;
for(int i=1;i<=128;i<<=1){
x=0,y=0,c=rd()%(n-1)+1;
for(int j=1;j<=i;j++){
x=f(f(x,c,n),c,n),y=f(y,c,n);
d=mul(d,abs(x-y),n);
}
if(__gcd(d,n)!=1)return __gcd(d,n);
}
}
}
非常好 Pollard-Rho，这使我的旋转。
C
给定串 \(s\)，每次问 \(t\) 在 \(s\) 中的出现次数，强制在线。
\(|s|,q,|t|,\sum |t|\le 10^5\)，\(|\Sigma|=10^6\).
\(\sum |t|\) 很小，考虑对所有询问串的长度的出现次数分治。小的暴力 kmp，大的哈希。
最劣也就是 \(O(n\sqrt{n}\log n)\) 小常数。
D
给出长 \(n\) 的排列 \(S,G\) 和数 \(k\).
对于 \(i\in[n-k+1,n]\)，可以将 \(G[i:n]\) 随机打乱，最大化如下区间 \([l,r]\) 的个数：
- 存在 \(S[x:y]\) 重排后与 \(G[l:r]\) 相同。
\(k\le n\le 2\times 10^5\).