有 组数据,每组数据有一个长度为 的 字符串,求构造一个 个结点的树满足每个结点的度数的奇偶性符合 串 ,且将这些点依次排列到一个环上,任意两条边不在非端点处相交。
。
ABC257G Prefix Concatenation 做题记录
给定仅存在小写英文字母的字符串 S,T。你需要将 T 分割成 k 个 S 的前缀(或着说用 $ S $ 的若干个前缀组成 T),最小化 k,输出最小值。若 k 不存在输出
-1
。1≤∣S∣,∣T∣≤5×105
ABC235G Gardens 做题记录
有三种不同颜色的球,分别有 A,B,C 个。(相同颜色的球之间不区分)
将球放入 N 个不同的盒子中,要求:
每个盒子至少放了一个球
每个盒子不能存在两个相同颜色的球
可以不放完所有的球
求放置方案数对 998244353 取模的结果。
1≤N≤5×106,0≤A,B,C≤N
ABC232G Modulo Shortest Path 做题记录
有一个 n 个节点的有向图 G,对于所有的 1≤i,j≤n 且 i=j,都有一条权值为 (ai+bj)modm 的边连接 i 和 j,请你求出 G 从 1 到 n 的最短路。
CF1065E Side Transmutations 做题记录
考虑一个字符集合A(A中元素互不相同)和一个长度为n的字符串S,其中S中的字符都属于集合A。
给你一个包含 m 个整数的序列 b (b1<b2<⋯<bm)。你可以对字符串 S 作以下的操作:
1.选择一个合法的 i ,并且令 k=bi ;
2.取出 S 中前 k 个字符 Prk ;
3.取出 S 中后 k 个字符Suk ;
4.将 S 中前 k 个字符替换成翻转后的 Suk ;
5.将 S 中后 k 个字符替换成翻转后的 Prk ;
举个例子,我们令 S= "abcdefghi",k=2 。这时Pr2= "ab",Su2= "hi",翻转后有 Pr2= "ba",Su2= "ih",那么最终得到的字符串 S 就是 "ihcdefgba"。
这个操作可以被执行许多次(可能是零次),任何一个 i 也可以被使用多次。
我们将字符串 S 和 T 称为相等的字符串,当且仅当存在一个操作序列,将字符串 S 变成 T。对于上面的例子来说,"abcdefghi" 和 "ihcdefgba" 是相等的。注意到 S 和它自己也是相等的。
你的任务很简单,数出互不相同的字符串的个数。
最终的答案可能会非常大,因此你只需要输出答案 mod 998244353 的结果。
2≤n≤109,1≤m≤min(2n,2∗105),1≤∣A∣≤109。