#894621 (Go) No.2388 At Least K-Characters

提出ソース

結果

問題	No.2388 At Least K-Characters
ユーザー	ynm3n
提出日時	2023-07-22 17:25:55
言語	Go (1.22.1)
結果	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

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,812 KB
testcase_01	AC	1 ms 6,816 KB
testcase_02	AC	1 ms 6,940 KB
testcase_03	AC	1 ms 6,940 KB
testcase_04	AC	2 ms 6,944 KB
testcase_05	AC	1 ms 6,944 KB
testcase_06	AC	2 ms 6,940 KB
testcase_07	AC	2 ms 6,944 KB
testcase_08	AC	1 ms 6,940 KB
testcase_09	AC	1 ms 6,944 KB
testcase_10	AC	1 ms 6,944 KB
testcase_11	AC	2 ms 6,940 KB
testcase_12	AC	1 ms 6,944 KB
testcase_13	AC	4 ms 6,940 KB
testcase_14	AC	3 ms 6,944 KB
testcase_15	AC	3 ms 6,940 KB
testcase_16	AC	674 ms 131,784 KB
testcase_17	AC	738 ms 131,656 KB
testcase_18	AC	677 ms 131,784 KB
testcase_19	AC	682 ms 131,788 KB
testcase_20	AC	717 ms 131,784 KB
testcase_21	AC	812 ms 131,788 KB
testcase_22	AC	803 ms 131,732 KB
testcase_23	AC	805 ms 131,732 KB
testcase_24	AC	749 ms 131,788 KB
testcase_25	AC	679 ms 131,784 KB
testcase_26	AC	785 ms 131,784 KB
testcase_27	AC	765 ms 131,784 KB
testcase_28	AC	788 ms 131,732 KB
testcase_29	AC	731 ms 131,784 KB
testcase_30	AC	712 ms 131,788 KB
testcase_31	AC	699 ms 131,784 KB
testcase_32	AC	686 ms 131,736 KB
testcase_33	AC	684 ms 131,728 KB
testcase_34	AC	771 ms 131,788 KB
testcase_35	AC	819 ms 131,788 KB
testcase_36	AC	765 ms 131,732 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

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で割り切れる
*/

yukicoder

結果

テストケース

ソースコード