CF1119H Triple 做题记录

nn 个数组,每个数组里有 xxaia_iyybib_izzcic_i,保证 0ai,bi,ci<2k0\le a_i,b_i,c_i<2^k

对于每一个 0t<2k0\le t<2^k,求有多少种从 nn 个数组中分别选一个数的方式,使得这些数异或起来等于 tt,对 998244353998244353 取模。

1n1051\le n\le 10^51k171\le k\le 17

阅读全文 »

ARC163D Sum of SCC 做题记录

给定 n,mn,m,求满足以下条件的 nn 个点的有向图 GG 的个数:

  • GG 是个竞赛图,即 GG 没有重边和自环且对于所有 1i<jn1\le i<j\le n 均满足 (ij)G(i\to j)\in G(ji)G(j\to i)\in G 中只有一个满足;
  • 只有 mm(i,j)(i,j) 满足 1i<jn1\le i<j\le n(ij)G(i\to j)\in G
    求所有满足条件的 GG 中的强连通分量的个数和,对 998244353998244353 取模。
    1n301\le n\le 301mn(n1)21\le m\le \frac{n(n-1)}{2}
阅读全文 »

CF1720E Misha and Paintings 做题记录

给你一个 n×nn\times n 的矩阵 aa 和一个正整数 kk,你可以对 aa 进行任意次操作(可以不操作),操作的具体步骤如下:

  • 选择矩阵 aa 的一个正方形子矩阵;
  • 选择一个正整数数 xx,其中 1xn21\leq x\leq n^2
  • 将子矩阵内的所有元素修改为 xx

你需要求出使矩阵 aa 恰好包含 kk 个不同元素所需的最小操作次数。

1n500,1kn21\le n\le 500,1\le k\le n^2

阅读全文 »

CF1103C Johnny Solving 做题记录

给定一个 nn 个点 mm 条边的无向连通图(无重边自环)和一个 1kn1\le k\le nkk,每个点的度数至少为 33。你需要找到以下两个东西的其中一个:

  • 一条有 kk 个节点的链;
  • nk\lceil\frac{n}{k}\rceil 个环,满足每个环的大小 >3>3 且不是 33 的倍数,且每个环都有至少一个节点在这些环中仅出现一次;

1n2.5×105,1m5×105,1kn1\le n\le 2.5\times 10^5,1\le m\le 5\times 10^5,1\le k\le n

阅读全文 »

[ABC304Ex] Constrained Topological Sort 做题记录

nn 个点,每个点有 li,ril_i,r_i 两个值,有 mm 条有向边 (si,ti)(s_i,t_i),你要给每个点确定一个权值 aia_i,满足以下条件:

  • aia_inn 的排列;
  • 对于所有 1im1\le i\le m 均有 asi<atia_{s_i}<a_{t_i}
  • 对于所有 1in1\le i\le n 均有 liairil_i\le a_i\le r_i

判断无解。

2n2×1052\le n\le 2\times 10^50mmin(n(n1),4×105)0\le m\le \min(n(n-1),4\times 10^5)i=jsi=sji\not=j\Rightarrow s_i\not=s_j

阅读全文 »

CF1526E Oolimry and Suffix Array 做题记录

给定 nn 和字符集大小 kk 以及一个 0n10\sim n-1 的排列 sasa,求有多少个长 nn,字符集大小 kk ,从 00 开始标号的字符串 ss 满足把 a={0,1,2,,n1}a=\{0,1,2,\dots,n-1\} 按照 s[i,n1]s_{[i,n-1]} 字典序排序后满足 a=saa=sa

即生成的后缀数组是 sasa

1n,k2×1051\le n,k\le 2\times 10^5

阅读全文 »

CF1427E Xum 做题记录

一开始黑板上有一个正奇数 x (3x<106)x\ (3\le x<10^6),每次你可以选定黑板上已有的正整数 a,ba,b(可以相等),将 a+ba+baba \oplus b 写在黑板上,其中 \oplus 表示异或运算,最终目标是将 11 写在黑板上。要求写数字不超过 10510^5 次且写上的数字不超过 510185*10^{18}

阅读全文 »

GYM103371B Cilantro 做题记录

给定 nn 和两个长 nn0101SSTT

设入栈序列为 SS,出栈序列为 TT 的所有栈操作序列中,T1T_1 可能对应的 SS 中的下标集合为 AA

xAx\sum\limits_{x\in A}x

例如 S=100S=100T=001T=001 时答案为 55,因为共有 22 种栈操作序列满足入栈序列为 SS,出栈序列为 TT

  • 进,进,进,出,出,出,此时 T1T_1 来自 S3S_3
  • 进,进,出,进,出,出,此时 T1T_1 来自 S2S_2

所以答案为 3+2=53+2=5

1n5×1061\le n\le 5\times 10^6

阅读全文 »