Stage 8. Slovenia

F. Differences

• 设 S j , i S_{j,i} Sj,i​ 表示第 $j$ 个字符串第 $i$ 个字符； f i , c f_{i,c} fi,c​ 表示一个 $N$ 维 $0/1$ 向量，第 $j$ 维 $0/1$ 表示 S j , i S_{j,i} Sj,i​ 是否为 $c$；则若第 $j$ 个字符串符合条件，需要满足：
  ∑ 1 ≤ i ≤ M ∑ c ≠ S j , i f i , c = ( K , … , K , 0 , K , … , K ) （除第 j 个位置为 0 外其余位置为 K 的 N 维向量） \\sum\\limits_{1\\le i\\le M}\\sum\\limits_{c\\not = S_{j,i}} f_{i,c} = (K,\\dots,K,0,K,\\dots ,K)（除第 j 个位置为 0 外其余位置为 K 的 N 维向量） 1≤i≤M∑​c=Sj,i​∑​fi,c​=(K,…,K,0,K,…,K)（除第j个位置为0外其余位置为K的N维向量）

• 将 $N$ 维向量的第 $k$ 维用 p k p^k pk 哈希即可实现快速相加，时间复杂度 $\mathcal{O}(NM)$。

• Code

K. Skills in Pills

• 显然应当尽可能晚地吃药，主要需要解决冲突的问题。
• 容易通过调整法证明，冲突时只需要将其中一人吃药时间向前推一天即可，即一定不劣于向前推更多天的方案。
• 因而可以设 f i , 0 / 1 f_{i,0/1} fi,0/1​ 表示冲突时在第 $i$ 天吃药 $A/B$、前一天在吃另一种药所需的最少药片数，转移即找到下一次冲突的位置，不难发现每次的转移是本质相同的，可通过预处理 $\mathcal{O}(1)$ 转移。
• 时间复杂度 $\mathcal{O}(n)$。
• Code

Stage 12. Ōokayama

G. Range NEQ

• 考虑容斥原理，假设对于 $0\le i<N$，恰有 k i ( 0 ≤ k i ≤ M ) k_i(0\\le k_i \\le M) ki​(0≤ki​≤M) 个 $j$ 满足 $iM\le j<(i+1)M$， ⌊ j M ⌋ = ⌊ P j M ⌋ \\lfloor \\frac{j}{M} \\rfloor = \\lfloor \\frac{P_j}{M} \\rfloor ⌊Mj​⌋=⌊MPj​​⌋，不难得到总的方案数：
  ∑ 0 ≤ k 0 , k 1 , … , k N − 1 ≤ M ( − 1 ) ∑ 0 ≤ i < N k i ( N M − ∑ 0 ≤ i < N k i ) ! ∏ 0 ≤ i < N C M k i A M k i \\sum \\limits_{0\\le k_0,k_1,\\dots,k_{N-1}\\le M} (-1)^{\\sum \\limits_{0\\le i < N}k_i}(NM-\\sum \\limits_{0\\le i < N}k_i)!\\prod\\limits_{0\\le i < N}C_{M}^{k_i}A_{M}^{k_i} 0≤k0​,k1​,…,kN−1​≤M∑​(−1)0≤i<N∑​ki​(NM−0≤i<N∑​ki​)!0≤i<N∏​CMki​​AMki​​
• 对于对应 $N$ 元组为 ( k 0 ′ , k 1 ′ , … , k N − 1 ′ ) (k'_0,k'_1,\\dots,k'_{N - 1}) (k0′​,k1′​,…,kN−1′​) 的方案，考虑其被计入的次数，故容斥是正确的：
  ∏ 0 ≤ i < N ∑ 0 ≤ k ≤ k i ′ ( − 1 ) k C k i ′ k = ∏ 0 ≤ i < N [ k i ′ = 0 ] \\prod \\limits_{0\\le i < N}\\sum \\limits_{0 \\le k \\le k'_i}(-1)^{k}C_{k'_i}^k=\\prod\\limits_{0 \\le i < N}[k'_i =0] 0≤i<N∏​0≤k≤ki′​∑​(−1)kCki′​k​=0≤i<N∏​[ki′​=0]
• 将组合数展开，设多项式：
  F ( x ) = ∑ k = 0 M ( M ! ) 2 ( ( M − k ) ! ) 2 k ! ( − x ) k F(x) = \\sum \\limits_{k=0}^{M}\\frac{(M!)^2}{((M-k)!)^2k!}(-x)^k F(x)=k=0∑M​((M−k)!)2k!(M!)2​(−x)k
• 则答案可以表示为：
  ∑ k = 0 N M ( N M − k ) ! [ x k ] F N ( x ) \\sum \\limits_{k=0}^{NM}(NM-k)![x^k]F^N(x) k=0∑NM​(NM−k)![xk]FN(x)
• 做多项式快速幂即可，时间复杂度 $\mathcal{O}(NM\log (NM))$。
• Code