Solution of ABC 258 Ex

Powerless233 · 2022-10-27 14:55:21 · 题解

Description

求满足以下条件的序列数量（对 998244353 取模）：

• 只由奇数构成。

• 所有数和为 S。

• 所有的前缀和中不能出现 A 中的任意数字。

Analysis

先把第三个限制（即前缀和限制）和数据范围忽略，考虑一个朴素的算法。

设 f_{i} 表示当前和为 i 的序列数量，那么有：

（可以取的数只有 1,3,5,\dots）

边界有：

这个 dp 的复杂度是 O(S^2) 的，显然我们需要做一些优化。

Optimize 1

观察到，f_{i-1}+f_{i-3}+f_{i-5}+\dots 是可以在边求 f 的时候边维护的，我们设 s_{i} 表示 s_{i}=f_{i}+f_{i-2}+f_{i-4}+\dots ，则有：

这样，我们就在 O(S) 的时间内求出了答案。

但这还不够！ S 的级别为 10^{18} ，这个数据范围似乎在提示我们使用某种优化。

Optimize 2

观察到 f,s 的递推式都是不变的，没有额外限制，且数据范围在 10^{18} ，这些信息提示我们使用一种优化：

矩阵快速幂。

考虑我们需要维护的量：f_{i},s_{i-1},s_{i-2} ，那么可以构造出矩阵：

根据之前的递推关系，有系数矩阵：

用快速幂优化这个过程，我们就在 O(\log_{2}n) 的复杂度下求出了答案。

Back to the Origin

接下来考虑前缀和限制。

把 “前缀和不能为 a_{i}” 写为形式化的语言，其实就是 f_{a_{i}} = 0 。那么我们只需要在快速幂的中间，将 f_{i} = 0 即可。

时间复杂度 O(n+\log_{2}S)。

Code

#include <bits/stdc++.h>
#define LL long long
#define int long long
using namespace std;
inline LL read()
{
    LL res = 0, fl = 1;
    char ch = getchar();
    while (!(ch >= '0' && ch <= '9'))
    {
        if (ch == '-')
            fl = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
        res = (res << 3) + (res << 1) + ch - '0', ch = getchar();
    return res * fl;
}
inline LL max(LL a, LL b) { return a > b ? a : b; }
inline LL min(LL a, LL b) { return a < b ? a : b; }
const LL inf = 0x3f3f3f3f, mod = 998244353;
const LL N = 1e5 + 5, M = 4, si = 3;
LL n, m, a[N];
struct matrix
{
    int a[M][M];
    matrix()
    {
        memset(a, 0, sizeof a);
    }
    inline void build()
    {
        for (int i = 1; i <= si; i++)
        {
            a[i][i] = 1;
        }
    }
};
matrix operator*(const matrix &x, const matrix &y)
{
    matrix res;
    for (int i = 1; i <= si; i++)
    {
        for (int j = 1; j <= si; j++)
        {
            for (int k = 1; k <= si; k++)
            {
                res.a[i][j] += x.a[i][k] * y.a[k][j] % mod;
                res.a[i][j] %= mod;
            }
        }
    }
    return res;
}
matrix operator^(const matrix x, LL y)
{
    matrix base = x, res;
    res.build();
    while (y)
    {
        if (y & 1)
            res = base * res;
        base = base * base;
        y >>= 1;
    }
    return res;
}
signed main()
{
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    matrix trans, cur, tmp;
    trans.a[1][1] = 1, trans.a[1][2] = 0, trans.a[1][3] = 1;
    trans.a[2][1] = 1, trans.a[2][2] = 0, trans.a[2][3] = 1;
    trans.a[3][1] = 0, trans.a[3][2] = 1, trans.a[3][1] = 0;
    n = read(), m = read();
    cur.a[1][1] = 1, cur.a[2][1] = 0, cur.a[3][1] = 0;
    for (int i = 1; i <= n; i++)
    {
        a[i] = read();
        tmp = trans ^ (a[i] - a[i - 1]);
        cur = tmp * cur;
        cur.a[1][1] = 0;
    }
    tmp = trans ^ (m - a[n]);
    cur = tmp * cur;
    cout << cur.a[1][1] << '\n';
    return 0;
}