CF1603

vp 都打不起来了,别说现场了。

[A Di-visible Confusion]

solution

题面:给出 $n$ 个数,每次可以删掉一个数当且仅当这个数不是它所在下标加一的倍数。每删去一个数,它后面的数会向前移动一位。问能否将 $n$ 个数删完。

做法:首先会意识到如果第一个数删不掉那就永远删不掉了,也就是删掉任意一个数都不会对它前面的数有影响。那么考虑增量法。当前的数是可以被删完的,于是增加一个新的数到最后的位置,由于前面的数都可以被删完,所以如果新加的数可以被前面包括自己所在的某个下标不整除,那么前面按照一定顺序删,一定可以让这个数到达那个位置从而被删掉。而这个数被删掉也不会影响到原来的删除序列,所以问题转化成了如何判断一个数是不是 $\operatorname{lcm}_{i=1}^m i$ 的倍数,直接维护即可。时间复杂度 $O(n\log )$。

code
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
//2021.11.25 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
LL LCM[100];
int id;
const int N=1e5+10;
namespace MAIN{
int n;
int a[N];
inline void MAIN(){
n=read();
for(res i=1;i<=n;i++)a[i]=read();
for(res i=1;i<=n;i++){
res fl=0;
if(i<id){
if(a[i]%LCM[i+1]==0){puts("NO");return;}
}
}
puts("YES");
}
}
int main(){
LCM[1]=1;
for(res i=2;;i++){
LCM[i]=lcm(LCM[i-1],i);
if(LCM[i]>2e9){id=i;break;}
}
res Case=read();
while(Case--)MAIN::MAIN();
return 0;
}

[B Moderate Modular Mode]

solution

题面:给出 $T$ 组 $(x,y),x,y\leq 10^9$,问是否存在一个 $n$,满足 $1\leq n\leq 2\ast 10^{18}$ 且 $n\mod x=y\mod n$,输出 $n$。

做法:首先可以想到如果 $x>y$,则令 $n=x+y$ 即可。如果 $x=y$,令 $n=x$。若 $x<y$,我开始想的是令 $n=\frac{x+y}{2}$,那么就要求

发现这东西不一定成立,如果 $y\geq 3x$ 就不行了,然后我想到类似地,令 $n=\frac{3x+y}{2}$ 就可以推出更多了。以此类推,只需要令 $n=\frac{(2k+1)x+y}{2}$,$k$ 由 $\frac{y}{x}$ 决定就可以了。时间复杂度 $O(T)$。

code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//2021.11.25 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e5+10;
namespace MAIN{
inline void MAIN(){
res x=read(),y=read();
if(x==y)printf("%d\n",x);
else if(x>y)printf("%d\n",x+y);
else {
res t=y/x;
if(t&1);
else t--;
printf("%lld\n",(y+t*x)/2);
}
}
}

[C Extreme Extension]

solution

题面:对于长度为 $n$ 的数组 $b$ ,数组的 extreme 值是执行如下操作的最少次数,使得数组 $b$ 变成非降序:

1)选择 $1$ 个下标 $i$ ,2)用 $2$ 个数字 $x,y$ 替代 $b_i$ ,满足 $x+y=b_i$ ,3)从而数组 $b$ 的长度增加 $1$。

现在给定 $1$ 个长度为 $n$ 的数组 $a$ ,计算 $a$ 的所有非空子数组的 extreme 值的和。

做法:不知道为啥 vp 的时候不会这道题啊,好怪。我开始的时候一直想的是对半分肯定不劣,但忘记了应该平均分成若干块才是正确的,然后就卡住了。。。

最优情况肯定是把这一块平均分到和下一块一致的情况( 如果这一块高于后面那一块 ),于是就是最后一个元素是 $\lfloor \frac{a_i}{\lceil\frac{a_i}{a_{i+1}}\rceil}\rfloor$,一共分成 $\lceil \frac{a_i}{a_{i+1}}\rceil$ 块。设 $f_{i,x}$ 表示从后往前递推到第 $i$ 个,此时末尾元素大小为 $x$ 的答案。注意到一个数改变了几次可以持续利用到前面,所以转移也是较为容易的,即 $f_{i,x}=\sum_{y\geq x} f_{i+1,y}$。根据前面的分析,我们知道转移的位置只有 $O(\sqrt{A})$ 个,所以总复杂度就是 $O(n\sqrt{A})$ 了。

注意下它卡了 $O(n\sqrt{A})$ 的空间,要改成滚动数组。

code
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
//2021.11.25 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e5+10;
namespace MAIN{
int n;
int a[N];
vector<Pair> f[2];
inline void MAIN(){
res cur=0;
n=read(),vector<Pair>().swap(f[0]),vector<Pair>().swap(f[1]);
for(res i=1;i<=n;i++)a[i]=read();
res ans=0;
for(res i=n;i;i--){
f[cur].pb(mp(a[i],1));
res las=a[i];
for(auto x:f[cur^1]){
res num=(a[i]+x.fi-1)/x.fi,tran=a[i]/num;
add(ans,mul(i,mul(num-1,x.se)));
if(las==tran)add(f[cur].back().se,x.se);
else las=tran,f[cur].pb(mp(tran,x.se));
}
cur^=1,vector<Pair>().swap(f[cur]);
}
printf("%d\n",ans);
}
}

[D Artistic Partition]

solution

题面:对于两个正整数 $l,r(l\leq r)$ 定义 $c(l,r)$:满足 $l\leq i\leq j\leq r,\gcd(i,j)\geq l$ 的整数对 $(i,j)$ 的个数。$T$ 组询问,每次给定两个正整数 $n,k,1\leq k\leq n$ ,对于所有整数序列 $0=x_1<x_2<…<x_k<x_{k+1}=n$ ,计算 $\sum_{i=1}^k c(x_i+1,x_{i+1})$ 的最小值。

做法:先分析下 $c(l,r)$ 到底是个什么东西。考虑差分,右端点差分没啥效果,左端点差分可以发现 $c(l,r)-c(l+1,r)$ 是 $[l,r]$ 中 $\gcd=l$ 的数对个数,这东西可以直接推下式子,就是 $\sum_{i=1}^{\lfloor\frac{r}{l}\rfloor} \varphi(i)$,这东西可以预处理出来。

然后考虑 $f_{n,k}$ 表示答案,发现这东西是可以转移的,即 $f_{n,k}=\min(f_{j,k-1}+c(j+1,n))$。再观察一下 $c$,发现这东西竟然满足四边形不等式,于是整个 $f$ 就满足了决策单调性,直接按每个 $k$ 分治转移一下好了。不过这里好像 $k$ 很大,但实际不然。首先可以注意到 $c(l,r)\geq r-l+1$,另一方面我们倍增构造这个序列,那么如果能倍增到,这个 $f_{n,k}$ 一定就是 $n$。也就是说 $2^k>n$ 时,$f_{n,k}=n$。所以总复杂度就是 $O(n\log^2n)$ 了。可能很多人很奇怪为什么不带根号,我稍作分析了一下,分治的每一层是 $O(\sum \sqrt{r-l})$,这个东西 $\mathrm{Cauchy}$ 不等式一下应该是 $O(n)$ 级别的,而分治只有 $O(\log)$ 层,所以实际上整除分块根本不是瓶颈。所以总复杂度就是 $O(n\log^2 n)$。

code
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
//2021.11.25 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e5+10;
int phi[N],prim[N],tot,vis[N];
LL F[N],f[N][21];
namespace MAIN{
int n,k;
int a[N];
inline void MAIN(){
n=read(),k=read();
if(k>=20){printf("%d\n",n);return;}
printf("%lld\n",f[n][k]);
}
}
inline LL calc(res l,const res &R){
RG LL ret=0;
for(res r;l<=R;l=r+1)r=R/(R/l),ret+=F[R/l]*(r-l+1);
return ret;
}
void solve(res l,res r,res L,res R,const res &k){
if(l>r)return;
res mid=(l+r)>>1;
RG LL ret=calc(R+1,mid);
res pos=0;
RG LL mn=INF;
for(res i=min(mid,R);i>=L;--i){
ret+=F[mid/i];
if(ret+f[i-1][k-1]<=mn)mn=ret+f[i-1][k-1],pos=i;
}
f[mid][k]=mn;
solve(l,mid-1,L,pos,k),solve(mid+1,r,pos,R,k);
}
int main(){
phi[1]=1;
for(res i=2;i<=N-10;i++){
if(!vis[i])prim[++tot]=i,phi[i]=i-1;
for(res j=1;j<=tot&&prim[j]*i<=N-10;j++){
vis[prim[j]*i]=1;
if(i%prim[j])phi[prim[j]*i]=(prim[j]-1)*phi[i];
else {phi[prim[j]*i]=prim[j]*phi[i];break;}
}
}
for(res i=1;i<=N-10;i++)F[i]=F[i-1]+phi[i];
for(res i=1;i<=N-10;i++)f[i][1]=(LL)i*(i+1)/2;
for(res i=2;i<=20;i++)solve(1,N-10,1,N-10,i);
res Case=read();
while(Case--)MAIN::MAIN();
return 0;
}

[E A Perfect Problem]

solution

题面:一个序列被称为好序列当且仅当这个序列的最大值和最小值的积大于等于这个序列的所有数之和。一个序列被称为完全好的序列当且仅当它的所有子序列都是好序列,问长度为 $n$ 的每个数大小小于等于 $n+1$ 的完全好序列的个数。

做法:一大堆性质啊,不知道咋出出来的。

注意到一个性质,将一个合法好序列不降地排好序后,它是完全好序列的充要条件是这个排好序的序列的每个前缀都是好序列,证明是不太容易的,可以先从证明每个区间是好序列再推到前缀。

接着还要继续观察性质。另一个性质就是对于整个序列而言,有 $\max\cdot \min\geq \sum a_i\geq n\cdot \min$,可以推出 $\max \geq n$,取等时则要求 $\max=\min=n$,即 $a_i=n$,否则 $\max >n$。去掉全部为 $n$ 的情况,把这个性质推广到排好序的序列的每个前缀,于是就有 $a_i>i$。

这些性质还不太够,我们继续考虑每个前缀是好序列的条件。即

好像一下子啥也看不出来,注意到 $a_1\cdot a_i$ 实际可以理解成 $a_1$ 个 $a_i$ 相加,所以这条式子可以改写成

证明这是充要的,可以用第三条式子代入即可证明。

第三条式子仍然涉及到 $\sum a_i$,这还是 $O(n^2)$ 的。注意到左边有类似结构,将其移到右边,有

这样右边是 $O(n)$ 的,于是我们枚举 $a_1$,即等价于求序列 $b$,满足

这样就可以 $\mathrm{dp}$ 了。设 $f_{i,j,k}$ 表示当前 $\mathrm{dp}$ 到第 $i$ 个数, 当前和为 $j$,当前要放的数是 $k$,转移就是枚举要放几个 $k$。然后注意到我们这算的已经是递增的了,而原序列不递增,只需类似 $\mathrm{EGF}$ 般把阶乘放进转移式里即可。这转移是调和级数,不算枚举 $a_1$,则复杂度为 $O(n^3\log n)$。

实际上,会发现有答案的 $a_1$ 只有 $O(\sqrt{n})$,因为

于是 $a_1$ 就是 $O(\sqrt{n})$ 个,所以总复杂度就是 $O(n^{\frac{7}{2}}\log n)$。

code
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
//2021.11.30 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=202+10;
namespace MAIN{
int n;
int f[N][N][N];
int C[N][N];
inline void MAIN(){
n=read(),kcz=read();
for(res i=0;i<=n+1;i++){
C[i][0]=1;
for(res j=1;j<=i;j++)C[i][j]=Add(C[i-1][j-1],C[i-1][j]);
}
res ans=0;
for(res a1=max(1,n-int(2*sqrt(n)+1));a1<=n+1;a1++){
for(res i=a1;i<=n+1;i++)for(res j=0;j<=n;j++)for(res k=0;k<=a1-(n-j)*(i-a1);k++)f[i][j][k]=0;
f[a1][0][0]=1;
for(res i=a1;i<=n+1;i++)
for(res j=(i==a1)?0:(n-a1/(i-a1));j<=n;j++)
for(res k=0;k<=a1-(n-j)*(i-a1);k++)if(f[i][j][k]){
for(res p=(i==a1);p<=n-j;p++){
res now=p*(i-a1)+k;
if(now>a1||a1*(j+p)+now>a1*i)break;
if(j+p<n)add(f[i+1][j+p][now],mul(f[i][j][k],C[n-j][p]));
else add(ans,mul(f[i][j][k],C[n-j][p]));
}
}
}
printf("%d\n",ans);
}
}

[F October 18, 2017]

solution

题面:给出 $n,k,x$,问所有数小于 $2^k$ 满足任意一个子集的异或和不等于 $x$ 的 $n$ 元组的个数。

做法:题意等价于 $\mathbb{F}_2^k$ 中有多少个 $n$ 元向量组构成的空间里不包含 $x$。

注意到原序列有序。

容易想到讨论 $x$ 是否为 $0$,因为 $x$ 不为 $0$ 时则是向量空间了。

$x=0$ 时等价于 $n$ 元向量线性无关,于是一个个选过来,方案数就是 $\prod_{i=1}^n (2^k-2^{i-1})$。

若 $x$ 不为 $0$ 时,$n$ 元向量组就构成了一个向量空间,考虑维度为 $r$ 的不包含 $x$ 的向量空间基底数量,于是就类同上面的是

减去一个数是考虑基底不包含 $x$,即让 $x$ 作为第一维后的基底方案数。剩下来的 $n-r$ 个向量考虑被基底的前 $i$ 个向量线性表出,且考虑有几个。于是方案数就是

而熟知 $\mathrm{q-binomial}$ 的老哥会一眼看出这个东西是 $\mathrm{q-binomial}$ 的生成函数,所以直接就有

于是答案就是

这东西全部可以预处理出来,就做完了。即

其中 $[n]_2!=\prod_{i=1}^n (2^i-1)$。由于 $n$ 比较大,这里需要倒着乘回来。

而证明 $\mathrm{q-binomial}$ 生成函数的方式比较多,简单地就直接观察 $[t^{i}]$ 和 $[t^{i+1}]$ 间的递推关系可以得出。或者直接得到其 $\mathrm{GF}$ 的递推式,即设

再两边同取 $[t^n]$ 也就能得到递推式了。

时间复杂度 $O(n)$。

code
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
//2021.12.5 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e7+10;
int pw[N],fac[N],inv[N],INV[N];
namespace MAIN{
int n,k,x;
int f[N];
inline void MAIN(){
n=read(),k=read(),x=read();
if(!x){
if(n>k){puts("0");return;}
res ret=1;
for(res i=0;i<n;i++)ret=mul(ret,Add(pw[k],kcz-pw[i]));
printf("%d\n",ret);
return;
}
f[0]=1;
res p=min(n,k),PW=qpow(2,n),inv2=qpow(2);
for(res i=1;i<=p;i++)f[i]=mul(f[i-1],mul(Add(PW,kcz-1),INV[i])),PW=mul(PW,inv2);
res A=1,ans=1;
for(res r=1;r<=p;r++)A=mul(A,Add(pw[k],kcz-pw[r])),add(ans,mul(A,f[r]));
printf("%d\n",ans);
}
}