Contestant. Rank 1886. Rating -17.

A. Prefix and Suffix Array

题意

给定一个字符串的所有前缀和后缀，如 ，不包含其本身，判断原字符串是否是回文字符串。

思路

既然是前后缀，并且回文字符串的判断只需比较 和 区间对应的子串即可，所以我们只需拿出长度为 的两个字符串，将一个字符串反转后和另一个比较，相等即回文。

时间复杂度：

对应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

题意

给定一个长度为 的数组 ，定义操作为选择任意一个数字并将其加减 ，操作最多执行 次。输出一种方案操作后得到的数组，满足 不能被 整除。

思路

首先，不能出现 ，因为无论前面的数怎么改变，最后都会被 整除，所以遇到 改成 。

其次，奇数不能被偶数整除，而偶数可以被奇数整除，但该偶数 就不会被该奇数整除了（具体证明不清楚）。

最后，我们得到下面的结论：遇到整除，将后者加一，除非遇到 ，此时将前者加一。

时间复杂度：

对应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

题意

定义一个不递减序列 的 为 。给定一个长度为 的序列，对于所有 ，输出前 个数的所有子序列的最大 对应的最大子序列长度。

思路

首先，第一个数对应的答案一定是 ，这是毋庸置疑的。

那么，遍历到第二个数的时候，我们可以继续保持答案 ，也可以把答案更新为 ，此时对应为选第二个数或者都选，因为序列是不递减的。

那么，假设我们选了两个数，那么继续遍历到第三个数的时候，由于第二三两个数的乘积大于等于前两个数的乘积，所以答案是肯定大于等于 的，我们唯一需要判断的就是前一个数能不能放进来。

为什么不用再往前考虑呢？因为之前我们已经判断过了，比如说第二次只选了一个数，那么 ，也必定满足 。

因此，这道题就变得很好写了（

时间复杂度：

对应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

题意

对于一个数 ，由算术基本定理可知，它可以分解为 ，现将所有底数和指数拿出来作为一个序列 ，定义如上。

现在，给定上述序列，长度为 ，序列的顺序未知，输出所有可能的排序中， 的个数总和，。

思路

特判

首先，底数一定为不同的 个质数，所以拿到数据后，我们应该先将所有不同的质数找出，若数量不够，直接输出 。

指数的全排列问题

否则，我们假设已经选好了 个质数，来考虑一下指数怎么排。

这是一个含有重复数字的全排列问题，它有一个公式，套用在本题即为下面的称述：

1. 我们定义 为所有合数的数量的序列，遍历得到长度为 ，如 中，；

2. 同理， 为所有质数的数量的序列，长度为 ；

3. 考虑到有部分质数被拿走，作为了底数，所以部分 会减少一定的值。因为底数不能重复，所以最多减少 ，我们定义 为所有质数扣去底数后的数量的序列；

那么，最后的答案即为所有 的和。

简化问题

显然， 可以作为公因子提出，而剩余的数可以进行通分，提出 （注意这里是 ，不是 ，能提出的原因是 ），剩余的分子即为 个数里面选 个的所有组合的和，每个组合的值为其包含的元素的乘积。

因此，我们只需要在所有不同质数中挑选 个，求出所选数字的乘积，最后所有不同选择算得的乘积总和乘上之前提出的公因子即为答案。

当然，我们可以递归枚举，但是这样复杂度未免太高了。

如何递推

所有乘积的式子的元素顺序是不影响答案的，所以我们不妨按照序列的顺序将每个式子的元素排序。

如对于下面的序列，我们希望从这 个元素中选 个：

1 2 3 5 4

因为我们确定了元素的顺序，所以我们不妨来考虑一个特定的元素：。

对于一个乘积式子 ，我们将第三位填上 ，那么可以得到这些式子：，

也就是 。

也就是说，前面两项的选择只和 前面的数有关。

我们还可以将上面的式子提取一下：。

这时， 来到了第二位，它的结果和 的运算大同小异。

而对于类似于 在第 项的情况，我们可以假想地在序列前加上几个 ，这样对结果毫无影响，但却让 出现在了 的每一位。

事实上，我们可以加上含 的若干项，使所有数字均在 的每一位出现，而如果这样，那么我们可以枚举每一个数字位于哪一位，然后将 上一位 的 前 个选择 所得的答案乘上这个数字，得到 前 位的 前 个选择的乘积。

显然，我们还需要加上不选这个数字的情况，也就是前一个数字的前 个选择所推得的答案。

因而，上述思路可以用二维 实现， 表示前 个数的前 个选择的推算结果。

关于 部分，本思路正反递推都是可行的，下面给出正向递推的状态转移方程：

其中， 为所有不同的质数的数量的序列，下标从 开始。

优化复杂度

阶乘和阶乘逆元可以预处理得到，而质数的判断可以使用线性筛（欧拉筛），求逆元的话可以线性递推也可以快速幂。

时间复杂度：常数有点大的

对应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();
}

我人似了