TCO2015 Round 3B CommutativeMapping
题意输入一个长度为 $n$ 的数组 $g_i$，满足 $g_i \in [1,n]$。现在问有多少个长度为 $n$ 的数组 $f_i$，满足：$f_i \in [1,n]$$g_{f_i} = f_{g_i}$$n \leq 5000$题解看到 $g$ 的定义，立马想到建图连边 $i \to g_i$，这样连出的是一个基环内向树森林。可以先从特殊情况开始考虑。基环树的特殊情况无非就是树（某个...
题意输入一个长度为 $n$ 的数组 $g_i$，满足 $g_i \in [1,n]$。现在问有多少个长度为 $n$ 的数组 $f_i$，满足：$f_i \in [1,n]$$g_{f_i} = f_{g_i}$$n \leq 5000$题解看到 $g$ 的定义，立马想到建图连边 $i \to g_i$，这样连出的是一个基环内向树森林。可以先从特殊情况开始考虑。基环树的特殊情况无非就是树（某个...
题意有一个 $n \times n$ 的网格，初始时有 $k$ 个位置给定了字符 x 或 o 中的一种，其他的默认为空。现在问有多少种填格子方案使得对于每个格子，它四联通相邻的格子的 o 的数量都是偶数。对 $10^9+7$ 取模。$1 \leq n,k \leq 10^5$题解首先我们发现确定了第一行就能确定整个格子长什么样：我们设 o 为 $1$，x 为 $0$，那么相当于要求每个格子周...
题意有两个字符串 $s,t$，有一个人在玩游戏。他的目标是凑出串 $s$。初始他有一个空串，每次可以找出 $t$ 的一个子串接到这个串的后面，他会最小化他的操作。现在你想找到这样一个长度为 $n$ 的串 $s$，使得他需要的操作次数尽量大。$n \leq 10^{18},1 \leq |t| \leq 10^5$。题解显然先手每次都是暴力找到最长的能和当前这个后缀匹配的 $t$ 的子串然后贪...
A先将其压成二进制数，考虑两个人 $(i,j)$ 他们不可能拥有相同的通过数当且仅当它们不同的位的数量是奇数，也就是 $x\text{ xor } y$ 有奇数个 $1$。然后我赛时直接冲了个 FWT 过了稍微分析一下，发现两个数不同，当且仅当一个是 $1$ 一个是 $0$，我们只考虑这些不同的位置，发现恰好一个 $1$ 的数量是奇数一个是偶数。反过来也是对的。所以统计一下有奇数个 $1$ ...
A贪心填。先尽量填竖着的再填横着的。因为这样最多会浪费 $1$ 个，所以达到了答案的上界。求出上界判断是否 $\leq$ 即可。B枚举一个位置 $i$，前面只保留 $0$ 后面只保留 $1$，判断是否合法即可。C首先第一步横着走还是竖着走都是一样的。我们设第一步横着走。那么横着走只可能用奇数位置的 $c_i$，竖着走只可能用偶数位置的 $c_i$。枚举总共有几段，然后贪心选择最小的即可。注意...