結果

問題 No.2388 At Least K-Characters
ユーザー ynm3n
提出日時 2023-07-22 17:25:55
言語 Go
(1.23.4)
結果
AC  
実行時間 819 ms / 4,000 ms
コード長 5,925 bytes
コンパイル時間 18,113 ms
コンパイル使用メモリ 238,072 KB
実行使用メモリ 131,788 KB
最終ジャッジ日時 2024-07-05 04:17:50
合計ジャッジ時間 35,410 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

package main
import (
    "bufio"
    "fmt"
    "math"
    "math/big"
    "os"
    "strconv"
)
// 解答欄
func solve(sc *myScanner, wr *myWriter) {
    p := newModulus(998244353)
    n, m, k := sc.getInt3()
    as := func() []int {
        rs := sc.getRunes()
        res := make([]int, len(rs))
        for i, r := range rs {
            res[i] = int(r - 'a')
        }
        return res
    }()
    set := make(map[int]bool)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, 27)
    }
    dp[0][0] = 1
    for i := 0; i < m; i++ {
        for j := 0; j <= 26; j++ {
            x := dp[i][j]
            if i < n && len(set) == j {
                a := as[i]
                cntExist := 0
                for b := 0; b < a; b++ {
                    if set[b] {
                        cntExist++
                    }
                }
                dp[i+1][j] = p.add(dp[i+1][j], cntExist)
                if j+1 <= 26 {
                    dp[i+1][j+1] = p.add(dp[i+1][j+1], a-cntExist)
                }
                if set[a] {
                    dp[i+1][j] = p.add(dp[i+1][j], 1)
                } else {
                    dp[i+1][j+1] = p.add(dp[i+1][j+1], 1)
                }
                x = p.sub(x, 1)
            } else if i == n && len(set) == j {
                x = p.sub(x, 1)
            }
            dp[i+1][j] = p.add(dp[i+1][j], x*j)
            if j+1 <= 26 {
                dp[i+1][j+1] = p.add(dp[i+1][j+1], x*(26-j))
            }
        }
        if i < n {
            set[as[i]] = true
        }
    }
    ans := 0
    for i := 1; i <= m; i++ {
        for j := k; j <= 26; j++ {
            ans = p.add(ans, dp[i][j])
        }
    }
    if len(set) >= k {
        ans = p.sub(ans, 1)
    }
    wr.println(ans)
}
// modulo tools
type modulus int
const defaultModP = int(1e9) + 7
func newModulus(p int) *modulus {
    m := modulus(p)
    return &m
}
func (m *modulus) mod(a int) int {
    if a < 0 || a >= int(*m) {
        a %= int(*m)
    }
    if a < 0 {
        a += int(*m)
    }
    return a
}
func (m *modulus) add(a, b int) int { return m.mod(a + b) }
func (m *modulus) sub(a, b int) int { return m.mod(a - b) }
func (m *modulus) mul(a, b int) int { return m.mod(a * b) }
func (m *modulus) div(a, b int) int { return m.mul(a, m.inv(b)) }
func (m *modulus) inv(a int) int {
    x, _ := extGcd(a, int(*m))
    return x
}
func (m *modulus) pow(a, n int) int {
    res := 1
    b := m.mod(a)
    for n > 0 {
        if n&1 > 0 {
            res = m.mul(res, b)
        }
        n >>= 1
        b = m.mul(b, b)
    }
    return res
}
func extGcd(a, b int) (int, int) {
    x0, y0 := 1, 0
    x1, y1 := 0, 1
    for a%b != 0 {
        q := a / b
        r := a % b
        x2, y2 := x0-q*x1, y0-q*y1
        a, b = b, r
        x0, y0 = x1, y1
        x1, y1 = x2, y2
    }
    return x1, y1
}
// 入出力の準備(sc, wr)
func main() {
    sc := &myScanner{bufio.NewScanner(os.Stdin)}
    wr := &myWriter{bufio.NewWriter(os.Stdout)}
    startBufSize := 4096
    maxBufSize := math.MaxInt64
    sc.Buffer(make([]byte, startBufSize), maxBufSize)
    sc.Split(bufio.ScanWords)
    solve(sc, wr)
    wr.Flush()
}
// useful funcs for slice
func makeInts(n, x int) []int {
    res := make([]int, n)
    for i := range res {
        res[i] = x
    }
    return res
}
func makeBools(n int, b bool) []bool {
    res := make([]bool, n)
    for i := range res {
        res[i] = b
    }
    return res
}
func countTrue(bs []bool) int {
    res := 0
    for _, b := range bs {
        if b {
            res++
        }
    }
    return res
}
// input
type myScanner struct {
    *bufio.Scanner
}
func (sc *myScanner) getInt() int {
    return sc._getIntOffset(0)
}
func (sc *myScanner) getInt2() (int, int) {
    return sc.getInt(), sc.getInt()
}
func (sc *myScanner) getInt3() (int, int, int) {
    return sc.getInt(), sc.getInt(), sc.getInt()
}
func (sc *myScanner) getInt4() (int, int, int, int) {
    return sc.getInt(), sc.getInt(), sc.getInt(), sc.getInt()
}
func (sc *myScanner) getInts(n int) []int {
    return sc._getIntsOffset(n, 0)
}
func (sc *myScanner) getIntZeroIndexed() int {
    return sc._getIntOffset(-1)
}
func (sc *myScanner) getIntsZeroIndexed(n int) []int {
    return sc._getIntsOffset(n, -1)
}
func (sc *myScanner) _getIntOffset(x int) int {
    res, err := strconv.Atoi(sc.getString())
    if err != nil {
        panic(err)
    }
    return res + x
}
func (sc *myScanner) _getIntsOffset(n, x int) []int {
    res := make([]int, n)
    for i := range res {
        res[i] = sc._getIntOffset(x)
    }
    return res
}
func (sc *myScanner) getString() string {
    sc.Scan()
    return sc.Text()
}
func (sc *myScanner) getStrings(n int) []string {
    res := make([]string, n)
    for i := range res {
        res[i] = sc.getString()
    }
    return res
}
func (sc *myScanner) getRunes() []rune {
    return []rune(sc.getString())
}
func (sc *myScanner) getFloat() float64 {
    res, err := strconv.ParseFloat(sc.getString(), 64)
    if err != nil {
        panic(err)
    }
    return res
}
func (sc *myScanner) getFloats(n int) []float64 {
    res := make([]float64, n)
    for i := range res {
        res[i] = sc.getFloat()
    }
    return res
}
// output
type myWriter struct {
    *bufio.Writer
}
func (wr *myWriter) println(a ...interface{}) {
    fmt.Fprintln(wr, a...)
}
func (wr *myWriter) printf(format string, a ...interface{}) {
    fmt.Fprintf(wr, format, a...)
}
// simple math funcs for int
func max(as ...int) int {
    res := as[0]
    for _, a := range as {
        if res < a {
            res = a
        }
    }
    return res
}
func min(as ...int) int {
    res := as[0]
    for _, a := range as {
        if res > a {
            res = a
        }
    }
    return res
}
func chMax(a *int, b int) {
    *a = max(*a, b)
}
func chMin(a *int, b int) {
    *a = min(*a, b)
}
func abs(a int) int {
    if a < 0 {
        return -a
    }
    return a
}
func pow(a, n int) int {
    res := 1
    b := a
    for n > 0 {
        if n&1 > 0 {
            res *= b
        }
        n >>= 1
        b *= b
    }
    return res
}
func sum(s ...int) int {
    res := 0
    for _, v := range s {
        res += v
    }
    return res
}
func checkPrime(a int) bool {
    if a == 2 {
        return true
    } else if a%2 == 0 {
        return false
    }
    res := true
    for q := 3; q*q <= a; q += 2 {
        if a%q == 0 {
            res = false
            break
        }
    }
    return res
}
func toBInt(a int) *big.Int {
    return big.NewInt(int64(a))
}
/*
    めも
    int(64)の最大値: 9223372036854775807 = (2^63 - 1)
    19桁
    10^18 < 2^60 < 2^63 < 10^19
    10^19 はintだとオーバーフローする
    sliceの長さ: 10^8程度までは許される
    型によるがそれ以上は Out of memory の危険がある
    1~nの和: {n*(n+1)}/2
    (1~nの平均値)*n を式変形したもの
    先に掛け算をすることで必ず2で割り切れる
*/
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0