結果

問題 No.1186 長方形の敷き詰め
コンテスト
ユーザー ID 21712
提出日時 2026-06-05 14:37:36
言語 Go
(1.26.1)
コンパイル:
env GOCACHE=/tmp go build _filename_
実行:
./Main
結果
AC  
実行時間 12 ms / 2,000 ms
コード長 868 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 14,616 ms
コンパイル使用メモリ 283,424 KB
実行使用メモリ 9,856 KB
最終ジャッジ日時 2026-06-05 14:37:52
合計ジャッジ時間 12,450 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge1_0
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

package main

import . "fmt"

const MOD = 998244353

func main() {
	var n,m int
	Scan(&n,&m)
	if n > m || n == 1 {
		Println(1)
		return
	}
	dp := make([]int, m+1)
	dp[0] = 1
	for i := 0; i < m; i++ {
		if i+n < len(dp) {
			dp[i+n] = (dp[i+n]+dp[i])%MOD
		}
		dp[i+1] = (dp[i+1]+dp[i])%MOD
	}
	Println(dp[m])	
}

/*
考察

NもMも最大10^9だと勘違いして考察してて解法わからん、となっていたが
誤読でありMは最大10^6だった
これだったら普通にDP

DP[x+N] += DP[x]
DP[x+1] += DP[x]

位置x時点までの組み合わせから
パーツN個まとめて横に積んで使う
or
パーツ1個縦のまま使う
をやるだけ

なお N > M ならパーツ全部を縦に積めるだけの1通り

普通にWA

勘違い考察のときN=1のケースについてコーナーケースだと認識していたのにド忘れ

*/
0