字符串题解

• 2020 年 8 月 8 日
• 笔记
• 数学，数论, 题解

题目大意

求有多少个长度为 \(n\) ，仅包含前 \(k\) 个小写字母且包含至少一个长度不少于 \(2\) 的回文串的字符串作为子串。对于 \(k>26\) 的情况，你只需要把每个字母当成一个与其他字母均不同的字母，而无需关注它具体是什么符号。答案需要对 \(998244353\)（一个质数）取模。

\(1\le n,k \le 10^9\)

example
in
3 3
out
21

分析

看到数据范围，发现数学题没跑。开始找规律

3 3
1  1  123
   2  12
   3  13
2  1  12
   2  123
   3  23
3  1  13
   2  23
   3  123
大概就是3*3*3-3*2

然后再推个几下就会发现式子

\(ans=k^n-k*(k-1)*(k-2)^{(n-2)}\)

然后写代码就是有手就行

#include <bits/stdc++.h>
#define MOD 998244353
#define int long long
using namespace std ;
int n , k ;
inline int Pow ( int a , int b ) {
    a %= MOD ; b %= MOD - 1 ;
    int res = 1 ;
    while ( b ) {
        if ( b & 1 ) res = res * a % MOD ;
        b >>= 1 ;
        a = a * a % MOD ;
    }
    return res ;
}
signed main () {
    cin >> n >> k ;
    if ( n == 1 ) cout << 0 << endl ; // 特判
    else if ( n == 2 ) cout << k % MOD << endl ;
    else {
        int ans = Pow ( k , n ) - ( ( k * ( k - 1 ) % MOD ) * Pow ( k - 2 , n - 2 ) % MOD ) % MOD ;
        cout << ( ans + MOD ) % MOD << endl ; // 避免出现负数
    }
}