CodeForces 1065E. Side Transmutations 计数

昨天不该早点走的....

首先操作限制实际上是一个回文限制

每个$b[i] - b[i - 1]$互不干扰，不妨设这个串关于中心点对称的这么一对区间的串分别为$(S_1, S_2)$

题目的限制相当与存在$(T_1, T_2)$使得$T_1 = inv(S_2) \;and\;T_2 = inv(S_1)$

考虑一对串$(S_1, S_2)$被计数多少次，我们分类讨论一下

一个长为$L$的子串的方案数为$S^L$，即为$f(L)$

一个长为$L$,字符集为$S$的区间，形成回文串的方案数为$S^{\frac{L +1}{2}}$，记为$g(L)$

如果$(S_1, S_2)$中有两个回文串，会被算重0次，否则都会被算重1次

那么方案数为$(f(L)^2 - g(L)^2) / 2 + g(L) * g(L)$

化简一下，$f(L) * (f(L) + 1) / 2$

复杂度$O(n \log n)$

#include <vector>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

namespace remoon {

    #define re register

    #define de double

    #define le long double

    #define ri register int

    #define ll long long

    #define sh short

    #define pii pair<int, int>

    #define mp make_pair

    #define pb push_back

    #define tpr template <typename ra>

    #define rep(iu, st, ed) for(ri iu = st; iu <= ed; iu ++)

    #define drep(iu, ed, st) for(ri iu = ed; iu >= st; iu --)

    extern inline char gc() {

        static char RR[], *S = RR + , *T = RR + ;

        if(S == T) fread(RR, , , stdin), S = RR;

        return *S ++;

    }

    inline int read() {

        int p = , w = ; char c = gc();

        while(c > '' || c < '') { if(c == '-') w = -; c = gc(); }

        while(c >= '' && c <= '') p = p *  + c - '', c = gc();

        return p * w;

    }

    int wr[], rw;

    #define pc(iw) putchar(iw)

    tpr inline void write(ra o, char c = '\n') {

        if(!o) pc('');

        if(o < ) o = -o, pc('-');

        while(o) wr[++ rw] = o % , o /= ;

        while(rw) pc(wr[rw --] + '');

        pc(c);

    }

    tpr inline void cmin(ra &a, ra b) { if(a > b) a = b; }

    tpr inline void cmax(ra &a, ra b) { if(a < b) a = b; }

    tpr inline bool ckmin(ra &a, ra b) { return (a > b) ? a = b,  : ; }

    tpr inline bool ckmax(ra &a, ra b) { return (a < b) ? a = b,  : ; }

}

using namespace std;

using namespace remoon;

#define mod 998244353

#define iv2 499122177

#define sid 200050

inline int fp(int a, int k) {

    int ret = ;

    for( ; k; k >>= , a = 1ll * a * a % mod)

        if(k & ) ret = 1ll * ret * a % mod;

    return ret;

}

int n, m, S;

int b[sid];

int main() {

    n = read(); m = read(); S = read();

    rep(i, , m) b[i] = read();

    int ans = fp(S, n - (b[m] * ));

    rep(i, , m) {

        int L = b[i] - b[i - ];

        ans = 1ll * ans * fp(S, L)  % mod * (fp(S, L) + )  % mod * iv2 % mod;

    }

    write(ans);

    return ;

}

巴特西

CodeForces 1065E. Side Transmutations 计数

最新文章

热门文章