CF1682D Circular Spanning Tree 做题记录

TT 组数据,每组数据有一个长度为 nn01\tt 01 字符串,求构造一个 nn 个结点的树满足每个结点的度数的奇偶性符合 01\tt 01ss,且将这些点依次排列到一个环上,任意两条边不在非端点处相交。

1n2×1051\le n\le 2\times 10^5

阅读全文 »

ABC258Ex Odd Steps 做题记录

给定 NNSS 和长度为 NN 的序列 AA,找到满足以下条件的序列 XX 的个数对 998244353998244353 取模后的结果:

  • XX 的每个元素都是正奇数
  • Xi=S\sum X_i=S
  • Yi=j=1iXjY_i=\sum\limits_{j=1}^iX_j,那么对于所有 1iX,1jN1\le i\le |X|,1\le j\le Ni,ji,j,都满足 Yi=AjY_i\not=A_j

1N1051\le N\le 10^5

1A1<A2<<AN<S10181\le A_1<A_2<\dots<A_N<S\le10^{18}

阅读全文 »

ABC257G Prefix Concatenation 做题记录

给定仅存在小写英文字母的字符串 S,TS, T。你需要将 TT 分割成 kkSS 的前缀(或着说用 $ S $ 的若干个前缀组成 TT),最小化 kk,输出最小值。若 kk 不存在输出 -1

1S,T5×1051 \leq |S|,|T| \leq 5\times 10^5

阅读全文 »

ABC235G Gardens 做题记录

有三种不同颜色的球,分别有 A,B,CA,B,C 个。(相同颜色的球之间不区分)

将球放入 NN 个不同的盒子中,要求:

  • 每个盒子至少放了一个球

  • 每个盒子不能存在两个相同颜色的球

  • 可以不放完所有的球

求放置方案数对 998244353998244353 取模的结果。

1N5×1061 \leq N \leq 5 \times 10^60A,B,CN0 \leq A,B,C \leq N

阅读全文 »

CF1065E Side Transmutations 做题记录

考虑一个字符集合AAAA中元素互不相同)和一个长度为nn的字符串SS,其中SS中的字符都属于集合AA

给你一个包含 mm 个整数的序列 bb (b1<b2<<bmb_1<b_2<\dots<b_m)。你可以对字符串 SS 作以下的操作:

1.选择一个合法的 ii ,并且令 k=bik=b_i ;

2.取出 SS 中前 kk 个字符 PrkPr_k ;

3.取出 SS 中后 kk 个字符SukSu_k ;

4.将 SS 中前 kk 个字符替换成翻转后的 SukSu_k ;

5.将 SS 中后 kk 个字符替换成翻转后的 PrkPr_k ;

举个例子,我们令 S=S= "abcdefghi",k=2k=2 。这时Pr2=Pr_2= "ab",Su2=Su_2= "hi",翻转后有 Pr2=Pr_2= "ba",Su2=Su_2= "ih",那么最终得到的字符串 SS 就是 "ihcdefgba"。

这个操作可以被执行许多次(可能是零次),任何一个 ii 也可以被使用多次。

我们将字符串 SSTT 称为相等的字符串,当且仅当存在一个操作序列,将字符串 SS 变成 TT。对于上面的例子来说,"abcdefghi" 和 "ihcdefgba" 是相等的。注意到 SS 和它自己也是相等的。

你的任务很简单,数出互不相同的字符串的个数。

最终的答案可能会非常大,因此你只需要输出答案 modmod 998244353998244353 的结果。

2n1092 \leq n \leq 10^91mmin(n2,2105)1 \leq m \leq min(\frac{n}{2},2 * 10^5)1A1091\leq |A|\leq 10^9

阅读全文 »