結果

問題 No.2636 No Waiting in Vain
ユーザー ynm3n
提出日時 2024-02-18 14:33:11
言語 Go
(1.23.4)
結果
AC  
実行時間 17 ms / 2,000 ms
コード長 5,899 bytes
コンパイル時間 11,078 ms
コンパイル使用メモリ 229,632 KB
実行使用メモリ 7,624 KB
最終ジャッジ日時 2024-09-29 00:29:18
合計ジャッジ時間 12,882 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 44
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

package main

import (
	"bufio"
	"fmt"
	"io"
	"math"
	"os"
	"strconv"
)

// 解答欄
func solve(in *input, out, outErr *output) {
	m := newModulus(mod998_244_353)
	n, k := in.nextInt2()
	s := make([]rune, n+1)
	s[0] = 'P'
	copy(s[1:], in.nextRunes())

	cntT := 0
	cntN := 0
	for i := 1; i <= n; i++ {
		if s[i] == 'N' {
			cntN++
			if s[i-1] != 'C' {
				cntT++
			}
		}
	}

	combi, _ := m.newCombinationCalculator(cntT)

	ans := 0
	for i := 1; (cntN-i) >= k && (cntT-i) >= 0; i++ {
		tmp := combi(cntT, i)
		ans = m.add(ans, tmp)
	}
	out.println(ans)
}

// 以下のサイト様のアルゴリズムを真似させていただきました
// https://drken1215.hatenablog.com/entry/2018/06/08/210000
func (mAddr *modulus) newCombinationCalculator(n int) (func(n, k int) int, struct{ fac, finv, inv []int }) {
	m := int(*mAddr)
	n++
	fac := make([]int, n)
	finv := make([]int, n)
	inv := make([]int, n)
	if n == 1 {
		fac[0], finv[0] = 1, 1
	} else {
		fac[0], fac[1] = 1, 1
		finv[0], finv[1] = 1, 1
		inv[1] = 1
		for i := 2; i < n; i++ {
			fac[i] = fac[i-1] * i % m
			inv[i] = m - inv[m%i]*(m/i)%m
			finv[i] = finv[i-1] * inv[i] % m
		}
	}

	f := func(n, k int) int {
		if (n < k) || (n < 0) || (k < 0) {
			return 0
		}
		return fac[n] * (finv[k] * finv[n-k] % m) % m
	}
	s := struct {
		fac  []int
		finv []int
		inv  []int
	}{fac, finv, inv}
	return f, s
}

// modulo tools
type modulus int

const mod1_000_000_007 = 1_000_000_007
const mod998_244_353 = 998_244_353

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 m.mod(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
}

// 入出力の準備(in, out, outErr)
func main() {
	const (
		// インタラクティブ問題の時 true
		// バッファ無し出力に変更する。入力は変わらない
		interactiveProblem = false

		// 「X個のテストケースが与えられる」系の問題の時 true
		// 入力の一番最初でテストケース数が与えられる場合のみ使える
		variableSolveCount = false
	)

	const startBufSize = 4096
	const maxBufSize = math.MaxInt64
	in := &input{sc: bufio.NewScanner(os.Stdin)}
	in.sc.Buffer(make([]byte, startBufSize), maxBufSize)
	in.sc.Split(bufio.ScanWords)
	out := &output{}
	if interactiveProblem {
		out.w = os.Stdout
	} else {
		bw := bufio.NewWriter(os.Stdout)
		out.w = bw
		defer func() {
			if err := bw.Flush(); err != nil {
				panic(fmt.Errorf("flush error: %w", err))
			}
		}()
	}
	outErr := &output{w: os.Stderr}

	loop := 1
	if variableSolveCount {
		if _, err := fmt.Scan(&loop); err != nil {
			panic(fmt.Errorf("valiableSolveCount = %v, loop = %v: %w", variableSolveCount, loop, err))
		}
	}
	for i := 0; i < loop; i++ {
		solve(in, out, outErr)
	}
}

type input struct{ sc *bufio.Scanner }

func (in *input) nextString() string {
	in.sc.Scan()
	return in.sc.Text()
}
func (in *input) nextStrings(n int) []string {
	res := make([]string, n)
	for i := range res {
		res[i] = in.nextString()
	}
	return res
}
func (in *input) nextRunes() []rune {
	return []rune(in.nextString())
}
func (in *input) nextInt() int {
	s := in.nextString()
	res, err := strconv.Atoi(s)
	if err != nil {
		panic(fmt.Errorf("in.nextInt: %w", err))
	}
	return res
}
func (in *input) nextInts(n int) []int {
	res := make([]int, n)
	for i := range res {
		res[i] = in.nextInt()
	}
	return res
}
func (in *input) nextFloat() float64 {
	s := in.nextString()
	res, err := strconv.ParseFloat(s, 64)
	if err != nil {
		panic(fmt.Errorf("in.nextFloat: %w", err))
	}
	return res
}
func (in *input) nextFloats(n int) []float64 {
	res := make([]float64, n)
	for i := range res {
		res[i] = in.nextFloat()
	}
	return res
}
func (in *input) nextInt2() (int, int) {
	return in.nextInt(), in.nextInt()
}
func (in *input) nextInt3() (int, int, int) {
	return in.nextInt(), in.nextInt(), in.nextInt()
}
func (in *input) nextInt4() (int, int, int, int) {
	return in.nextInt(), in.nextInt(), in.nextInt(), in.nextInt()
}

type output struct{ w io.Writer }

func (out *output) print(a ...any) {
	if _, err := fmt.Fprint(out.w, a...); err != nil {
		panic(fmt.Errorf("out.print: %w", err))
	}
}
func (out *output) printf(format string, a ...any) { out.print(fmt.Sprintf(format, a...)) }
func (out *output) println(a ...any)               { out.print(fmt.Sprintln(a...)) }

// simple math functions 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
}

// slice utility functions
func fillSlice[T any](s []T, v T) {
	for i := range s {
		s[i] = v
	}
}
func countSlice[T comparable](s []T, v T) int {
	res := 0
	for _, w := range s {
		if w == v {
			res++
		}
	}
	return res
}
0