問題一覧 > 通常問題

No.824 Many Shifts Hard

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 20
作問者 : PulmnPulmn / テスター : e869120e869120
2 ProblemId : 2449 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2019-04-26 23:41:32

問題文

$N+1$ 個のマスが横一列に並んでいて、左から順に $0,1,\dots,N$ と番号が振られています。また、$1$ 番目から $N$ 番目の各マスに $1$ つずつ駒が置かれています。
ここで、長さ $K$ の $1$ 以上 $N$ 以下の整数列 $A$ の得点を、次の操作を行った後の駒が $1$ 個以上置かれているマスの番号の総和 と定義します。

操作:$i=1,2,\dots,K$ の順番に $A_i$ 番目のマスにある全ての駒を $A_i-1$ 番目のマスに移す

長さ $K$ の $1$ 以上 $N$ 以下の整数列は $N^K$ 通りあります。
全ての整数列について得点を調べて、その総和を $10^9+7$ で割ったときの余りを求めてください。

入力

$N$ $K$

$1\le N\le 10^5$
$1\le K\le 300$

出力

全ての整数列における得点の総和を $10^9+7$ で割ったときの余りを出力してください。最後に改行してください。

サンプル

サンプル1
入力
6 4
出力
15110

$A=(6,6,5,1)$ の場合

$i=1$:$6$ 番目のマスには駒が $1$ つ置かれており、その駒を $5$ 番目のマスに移す
$i=2$:$6$ 番目のマスには駒が置かれていないので変化なし
$i=3$:$5$ 番目のマスには駒が $2$ つ置かれており、その駒を $4$ 番目のマスに移す
$i=4$:$1$ 番目のマスには駒が $1$ つ置かれており、その駒を $0$ 番目のマスに移す

最終的に、$0,2,3,4$ 番目のマスに $1$ つ以上の駒が置かれているので、整数列 $A=\{6,6,5,1\}$ の得点は $0+2+3+4=9$

サンプル2
入力
1 1
出力
0

サンプル3
入力
1000 100
出力
489487189

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。