Codeforces 1065E(计数)

题意

限定字符串长度为$n$，字符集规模为$A$，以及$m$个数字$b$，对于任意数字$bi$满足长度为$bi$的前缀和后缀先反转再交换位置后形成的新串与原串视作相等，问存在多少不同串。

思路

设$c[i]=b[i]-b[i-1]$，将字符串看成由长度$c[1],c[2],c[3]...n-2*b[m]...c[3],c[2],c[1]$串构成，那么只需考虑$c$中对应串的方案数和中间单独的方案数，相乘即答案。

假设考虑$k$位，形成回文的对应串有$A^{k}$，不形成的有$\frac{A^{2k}-A^{k}}{2}$，相加后得$\frac{A^{k}*(A^{k}+1)}{2}$，中间即$A^{n-2*b[m]}$。

代码

#include <bits/stdc++.h>

#define DBG(x) cerr << #x << " = " << x << endl;

const long long mod = 998244353;

const int maxn = 2e5+5;

using namespace std;

typedef long long LL;

LL n,m,A;

LL b[maxn];

LL qpow(LL a,LL b,LL p){

    LL res=1;

    while(b){

        if(b&1)res=(res*a)%p;

        a=a*a%p,b/=2;

    }return res;

}

int main(){

    scanf("%I64d%I64d%I64d",&n,&m,&A);

    for(int i=1;i<=m;i++)scanf("%I64d",&b[i]);

    LL ans=1,inv=qpow(2,mod-2,mod);

    for(int i=1;i<=m;i++){

        LL tmp=qpow(A,b[i]-b[i-1],mod);

        ans=ans*tmp%mod*(1+tmp)%mod*inv%mod;

    }

    ans*=qpow(A,n-2*b[m],mod);

    printf("%I64d\n",ans%mod);

    return 0;

}

巴特西

Codeforces 1065E(计数)

最新文章

热门文章