Contestant. Rank 1866. Rating -16.
A. Prefix and Suffix Array
题意
给定一个字符串的所有前缀和后缀，如 \(a, ab, abc, bca, ca, a\)，不包含其本身，判断原字符串是否是回文字符串。
思路
既然是前后缀，并且回文字符串的判断只需比较 \([0, \frac{n}{2}]\) 和 \([n - \frac{n}{2} - 1, n - 1]\) 区间对应的子串即可，所以我们只需拿出长度为 \(\frac{n}{2}\) 的两个字符串，将一个字符串反转后和另一个比较，相等即回文。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 998244353;
void solve(){
int n;
cin >> n;
vector<string> s;
for(int i=0;i<2 * (n - 1); i++){
string now;
cin >> now;
if(now.size() == n / 2) s.emplace_back(now);
}
std::reverse(s[0].begin(), s[0].end());
cout << (s[0] == s[1] ? "YES\n" : "NO\n");
}
signed main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int t;
cin >> t;
while(t --) solve();
}真是阴间时间下猪脑转不动了（
B. Not Dividing
题意
给定一个长度为 \(n\) 的数组 \(a\)，定义操作为选择任意一个数字并将其加减 \(1\)，操作最多执行 \(2n\) 次。输出一种方案操作后得到的数组，满足 \(a_{i + 1}\) 不能被 \(a_i\) 整除。
思路
首先，不能出现 \(1\)，因为无论前面的数怎么改变，最后都会被 \(1\) 整除，所以遇到 \(1\) 改成 \(2\)。
其次，奇数不能被偶数整除，而偶数可以被奇数整除，但该偶数 \(+1\) 就不会被该奇数整除了（具体证明不清楚）。
最后，我们得到下面的结论：遇到整除，将后者加一，除非遇到 \(1\)，此时将前者加一。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 998244353;
void solve(){
int n;
cin >> n;
int pre;
cin >> pre;
if(pre == 1) pre ++;
cout << pre << ' ';
for(int i=1;i<n;i++){
int cur;
cin >> cur;
if(cur == 1) cur ++;
if(cur % pre == 0){
pre = cur + 1;
}else pre = cur;
cout << pre << ' ';
}
cout << '\n';
}
signed main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int t;
cin >> t;
while(t --) solve();
}当然不是简简单单的判奇偶啊...
C. Scoring Subsequences
题意
定义一个不递减序列 \(s\) 的 \(cost\) 为 \(\frac{s_1\cdot s_2\cdot \ldots \cdot s_d}{d!}\)。给定一个长度为 \(n\) 的序列，对于所有 \(k \in [1, n]\)，输出前 \(k\) 个数的所有子序列的最大 \(cost\) 对应的最大子序列长度。
思路
首先，第一个数对应的答案一定是 \(1\)，这是毋庸置疑的。
那么，遍历到第二个数的时候，我们可以继续保持答案 \(1\)，也可以把答案更新为 \(2\)，此时对应为选第二个数或者都选，因为序列是不递减的。
那么，假设我们选了两个数，那么继续遍历到第三个数的时候，由于第二三两个数的乘积大于等于前两个数的乘积，所以答案是肯定大于等于 \(2\) 的，我们唯一需要判断的就是前一个数能不能放进来。
为什么不用再往前考虑呢？因为之前我们已经判断过了，比如说第二次只选了一个数，那么 \(a_2 \geq \frac{a_1 \times a_2}{2} => a_1 \leq 2\)，也必定满足 \(\frac{a_2 \times a_3}{2} \geq \frac{a_1 \times a_2 \times a_3}{2 \times 3} => a_1 \leq 3\)。
因此，这道题就变得很好写了（
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 998244353;
int a[N];
void solve(){
int n;
cin >> n;
for(int i=1;i<=n;i++) cin >> a[i];
vector<int> ans(n + 1);
ans[1] = 1;
for(int i=2;i<=n;i++){
ans[i] = ans[i - 1];
if(a[i - ans[i]] > ans[i]) ans[i] ++;
}
for(int i=1;i<=n;i++) cout << ans[i] << ' ';
cout << '\n';
}
signed main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int t;
cin >> t;
while(t --) solve();
}想个半天，差点没看到给的序列不递减，淦
D. Counting Factorizations
题意
对于一个数 \(m\)，由算术基本定理可知，它可以分解为 \(m=p_1^{e_1}\cdot p_2^{e_2}\cdot \ldots \cdot p_k^{e_k}\)，现将所有底数和指数拿出来作为一个序列 \(f(m) = \{p_1, e_1, p_2, e_2, \ldots \}\)，定义如上。
现在，给定上述序列，长度为 \(2n\)，序列的顺序未知，输出所有可能的排序中，\(m\) 的个数总和，\(\mod 998244353\)。
思路
特判
首先，底数一定为不同的 \(n\) 个质数，所以拿到数据后，我们应该先将所有不同的质数找出，若数量不够，直接输出 \(0\)。
指数的全排列问题
否则，我们假设已经选好了 \(n\) 个质数，来考虑一下指数怎么排。
这是一个含有重复数字的全排列问题，它有一个公式，套用在本题即为下面的称述：
我们定义 \(b\) 为所有合数的数量的序列，遍历得到长度为 \(s\)，如 \(2, 3, 4, 4\) 中，\(s = 1, b_1 = 2\)；
同理，\(c\) 为所有质数的数量的序列，长度为 \(t\)；
考虑到有部分质数被拿走，作为了底数，所以部分 \(c_i\) 会减少一定的值。因为底数不能重复，所以最多减少 \(1\)，我们定义 \(c'\) 为所有质数扣去底数后的数量的序列；
\(ans = \frac{n!}{b_1!\:\:b_2!\ldots b_s!\:\:c'_1!\:\:c'_2!\ldots c'_t!}\)
那么，最后的答案即为所有 \(ans\) 的和。
简化问题
显然，\(\frac{n!}{b_1!\:\:b_2!\ldots b_s!}\) 可以作为公因子提出，而剩余的数可以进行通分，提出 \(\frac{1}{c_1!\:\:c_2!\ldots c_t!}\)（注意这里是 \(c\)，不是 \(c'\)，能提出的原因是 \(x! = x * (x - 1)!\)），剩余的分子即为 \(t\) 个数里面选 \(n\) 个的所有组合的和，每个组合的值为其包含的元素的乘积。
因此，我们只需要在所有不同质数中挑选 \(n\) 个，求出所选数字的乘积，最后所有不同选择算得的乘积总和乘上之前提出的公因子即为答案。
当然，我们可以递归枚举，但是这样复杂度未免太高了。
如何递推
所有乘积的式子的元素顺序是不影响答案的，所以我们不妨按照序列的顺序将每个式子的元素排序。
如对于下面的序列，我们希望从这 \(5\) 个元素中选 \(3\) 个：
1 2 3 5 4因为我们确定了元素的顺序，所以我们不妨来考虑一个特定的元素：\(5\)。
对于一个乘积式子 \(? \times ? \times ?\)，我们将第三位填上 \(5\)，那么可以得到这些式子：\(1 \times 2 \times 5 + 1 \times 3 \times 5 + 2 \times 3 \times 5\)，
也就是 \((1 \times 2 + 1 \times 3 + 2 \times 3) \times 5\)。
也就是说，前面两项的选择只和 \(5\) 前面的数有关。
我们还可以将上面的式子提取一下：\((1 \times 2 + (1 + 2) \times 3) \times 5\)。
这时，\(3\) 来到了第二位，它的结果和 \(5\) 的运算大同小异。
而对于类似于 \(1\) 在第 \(3\) 项的情况，我们可以假想地在序列前加上几个 \(0\)，这样对结果毫无影响，但却让 \(1\) 出现在了 \([1, n]\) 的每一位。
事实上，我们可以加上含 \(0\) 的若干项，使所有数字均在 \([1, n]\) 的每一位出现，而如果这样，那么我们可以枚举每一个数字位于哪一位，然后将 上一位 的 前 \(x - 1\) 个选择 所得的答案乘上这个数字，得到 前 \(x\) 位的 前 \(x\) 个选择的乘积。
显然，我们还需要加上不选这个数字的情况，也就是前一个数字的前 \(x\) 个选择所推得的答案。
因而，上述思路可以用二维 \(dp\) 实现，\(dp[i][j]\) 表示前 \(i\) 个数的前 \(j\) 个选择的推算结果。
关于 \(dp\) 部分，本思路正反递推都是可行的，下面给出正向递推的状态转移方程：
\(dp[i][j] = dp[i][j] + dp[i - 1][j - 1] \times c[i]\)
其中，\(c\) 为所有不同的质数的数量的序列，下标从 \(1\) 开始。
优化复杂度
阶乘和阶乘逆元可以预处理得到，而质数的判断可以使用线性筛（欧拉筛），求逆元的话可以线性递推也可以快速幂。
时间复杂度：常数有点大的\(O(n ^ 2)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
const int N = 1e6 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 998244353;
bool vis[N], is[N];
int pri[N], cnt;
int fact[N], fact_inv[N];
int qp(int a, int b){
int ans = 1;
while(b > 0){
if(b & 1) ans = ((ans % mod) * (a % mod)) % mod;
a = ((a % mod) * (a % mod)) % mod;
b >>= 1;
}
return ans;
}
void init() {
for (int i = 2; i <= 1e6; ++i) {
if (!vis[i]) {
pri[cnt++] = i;
is[i] = true;
}
for (int j = 0; j < cnt; ++j) {
if (1ll * i * pri[j] > 1e6) break;
vis[i * pri[j]] = true;
if (i % pri[j] == 0) break;
}
}
fact[0] = fact_inv[0] = 1;
for(int i=1;i<=1e6;i++){
fact[i] = ((fact[i - 1] % mod) * (i % mod)) % mod;
fact_inv[i] = qp(fact[i], mod - 2);
}
}
void solve() {
int n;
cin >> n;
vector<int> in(2 * n);
map<int, int> tot;
for (int i = 0; i < 2 * n; i++) {
cin >> in[i];
tot[in[i]]++;
}
vector<int> c;
int el = fact[n];
for(auto e : tot){
if (is[e.first]) c.emplace_back(e.second);
el = ((el % mod) * (fact_inv[e.second] % mod)) % mod;
}
if (c.size() < n) {
cout << 0 << '\n';
return;
}
vector<vector<int>> dp(c.size() + 1, vector<int>(n + 1, 0));
dp[0][0] = 1;
for (int i = 1; i <= c.size(); i++) {
for (int j = 0; j <= n; j++) {
dp[i][j] = dp[i - 1][j];
if (j > 0) dp[i][j] = (dp[i][j] + dp[i - 1][j - 1] * c[i - 1]) % mod; //这里的c初始下标是0
}
}
cout << (el * dp[c.size()][n]) % mod << '\n';
}
signed main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
init();
int t = 1;
//cin >> t;
while(t --) solve();
}我人似了