Tenka1 Programmer Contest 2019 题解
C - Stones
题意
给定一个只由 . 和 # 组成的字符串 \(S\)，你可以修改若干字符使得不存在子串 #.。求最少修改次数。
\(|S|\le 2\times 10^5\)
题解
显然最后 \(S\) 一定是形如 ...### 的。求出前缀 # 的数量和后缀 . 的数量后枚举分界线计算即可。
时间复杂度 \(O(|S|)\)。
D - Three Colors
题意
有 \(N\) 个整数 \(A_i\)，将每个数染成红、绿、蓝三种颜色，记红、绿、蓝的数之和分别为 \(R,G,B\)，求使得 \(R,G,B\) 能组成一个面积为正数的三角形的染色方案数。对 \(998244353\) 取模。
\(N\le 300,A_i\le 300\)
题解
令 \(S\) 为所有数之和，那么染色方案合法当且仅当 \(R,G,B < \frac{S}{2}\)。
考虑容斥，用背包计算方案数即可。
时间复杂度 \(O(NS)\)。
E - Polynomial Divisors
题意
给定一个多项式 \(f(x)=\sum_{i=0}^{N}a_ix^i\)，求出所有的质数 \(p\) 满足对于任意整数 \(x\)，都有 \(p\mid f(x)\)。
\(N\le 10^4,a_i\le 10^9\)
题解
假设已经确定 \(p\)，考虑判断是否合法。根据费马小定理，当 \(x\not\equiv 0\pmod{p}\) 时，有 \(x^a\equiv x^{a\bmod (p-1)}\pmod{p}\)，那么我们可以将原多项式化为以下形式： \[ f(x)=\sum_{i=0}^{p-2}b_ix^i \]
那么 \(p\) 合法的充要条件是对于所有 \(0\le i < p-1\)，有 \(b_i\equiv 0\pmod{p}\)。充分性显然，必要性证明如下：
因为对于所有 \(0\le x < p\)，都有 \(f(x)\equiv 0\pmod{p}\)，相当于给定了多项式的 \(p\) 个点值 \((x,0)\)。由于 \(p\) 个点值可以唯一确定一个小于 \(p\) 次的多项式，而显然这个多项式一定是所有系数全 \(0\) 的多项式，所以必然有 \(b_i\equiv 0\pmod{p}\)。
于是我们枚举所有 \(N\) 以内的质数和所有系数的 \(\gcd\) 的质因子作为 \(p\) 进行判断即可。
时间复杂度 \(O(N(\pi(N)+\log a_i))\)，其中 \(\pi(N)\) 表示 \(N\) 以内质数数量。
F - Banned X
题意
求只包含 \(0,1,2\) 的，长度为 \(N\) 的，满足以下条件的序列数量：
- 不包含和为 \(X\) 的连续子序列。
对 \(998244353\) 取模。
\(N\le 3000\)
题解
令 \(f_{i,j}\) 表示长度为 \(i\)，和为 \(j\) 的方案数。\(j < X\) 可以直接转移，而 \(j=X\) 则一定为 \(0\)。接下来考虑 \(j > X\) 的情况。
注意到此时因为总和大于 \(X\)，若我们对该序列作前缀和，那么一定存在相邻两个前缀和分别为 \(X-1\) 和 \(X+1\)，假设位置为 \(k\) 和 \(k+1\)。此时第一个数和第 \(k+1\) 个数一定是 \(2\)，所以第 \(2\) 个数和第 \(k+2\) 个数也一定是 \(2\)……我们可以推出 \(k+1\) 到 \(n\) 和 \(1\) 到 \(n-k\) 这些数都是 \(2\)。
那么有 \(2(n-k)=j-(X-1)\)，我们可以唯一确定这个 \(k\)。于是就可以确定中间未填部分的长度与和，直接转移即可。
时间复杂度 \(O(N^2)\)。
