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\) 个质数,来考虑一下指数怎么排。

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

  1. 我们定义 \(b\) 为所有合数的数量的序列,遍历得到长度为 \(s\),如 \(2, 3, 4, 4\) 中,\(s = 1, b_1 = 2\)

  2. 同理,\(c\) 为所有质数的数量的序列,长度为 \(t\)

  3. 考虑到有部分质数被拿走,作为了底数,所以部分 \(c_i\) 会减少一定的值。因为底数不能重复,所以最多减少 \(1\),我们定义 \(c'\) 为所有质数扣去底数后的数量的序列;

  4. \(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();
}

我人似了