結果
問題 |
No.1964 sum = length
|
ユーザー |
|
提出日時 | 2022-06-23 22:27:01 |
言語 | Go (1.23.4) |
結果 |
AC
|
実行時間 | 83 ms / 2,000 ms |
コード長 | 1,075 bytes |
コンパイル時間 | 16,383 ms |
コンパイル使用メモリ | 232,012 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-07 16:10:01 |
合計ジャッジ時間 | 16,192 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 40 |
ソースコード
package main import ( "bufio" "fmt" "os" "strconv" ) var sc = bufio.NewScanner(os.Stdin) var out = bufio.NewWriter(os.Stdout) func computeDigits(x int) int { if x == 0 { return 0 } res := 0 for x > 0 { res++ x /= 10 } return res } func solve(n int) int { const p = 998244353 // fa <= 200+199 fa := n + (n - 1) w := make([]int, fa+1) for i := 1; i <= fa; i++ { w[i-computeDigits(i)+1]++ } //fmt.Println(w) dp := make([][]int, n+1) for i := 0; i <= n; i++ { dp[i] = make([]int, fa+1) } dp[0][0] = 1 for i := 0; i < n; i++ { for j := 0; j <= fa; j++ { for k := 1; k <= fa; k++ { nj := j + k if nj <= fa { dp[i+1][nj] += dp[i][j] * w[k] dp[i+1][nj] %= p } } } } //fmt.Println(dp) return dp[n][fa] } func main() { buf := make([]byte, 1024*1024) sc.Buffer(buf, bufio.MaxScanTokenSize) sc.Split(bufio.ScanWords) n := nextInt() ans := solve(n) PrintInt(ans) } func nextInt() int { sc.Scan() i, _ := strconv.Atoi(sc.Text()) return i } func PrintInt(x int) { defer out.Flush() fmt.Fprintln(out, x) }