結果
問題 | No.269 見栄っ張りの募金活動 |
ユーザー |
![]() |
提出日時 | 2020-09-30 17:04:38 |
言語 | Go (1.23.4) |
結果 |
AC
|
実行時間 | 68 ms / 5,000 ms |
コード長 | 3,273 bytes |
コンパイル時間 | 17,189 ms |
コンパイル使用メモリ | 224,024 KB |
実行使用メモリ | 17,408 KB |
最終ジャッジ日時 | 2024-07-06 04:29:56 |
合計ジャッジ時間 | 12,058 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 22 |
ソースコード
package mainimport ("bufio""fmt""os""strconv")func configure(scanner *bufio.Scanner) {scanner.Split(bufio.ScanWords)scanner.Buffer(make([]byte, 1000005), 1000005)}func getNextString(scanner *bufio.Scanner) string {scanned := scanner.Scan()if !scanned {panic("scan failed")}return scanner.Text()}func getNextInt(scanner *bufio.Scanner) int {i, _ := strconv.Atoi(getNextString(scanner))return i}func getNextInt64(scanner *bufio.Scanner) int64 {i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)return i}func getNextFloat64(scanner *bufio.Scanner) float64 {i, _ := strconv.ParseFloat(getNextString(scanner), 64)return i}func main() {fp := os.Stdinwfp := os.Stdoutextra := 0if os.Getenv("I") == "IronMan" {fp, _ = os.Open(os.Getenv("END_GAME"))extra = 100}scanner := bufio.NewScanner(fp)configure(scanner)writer := bufio.NewWriter(wfp)defer func() {r := recover()if r != nil {fmt.Fprintln(writer, r)}writer.Flush()}()solve(scanner, writer)for i := 0; i < extra; i++ {fmt.Fprintln(writer, "-----------------------------------")solve(scanner, writer)}}func solve(scanner *bufio.Scanner, writer *bufio.Writer) {n := getNextInt(scanner)s := getNextInt(scanner)k := getNextInt(scanner)s -= (n - 1) * n * k / 2if s < 0 {fmt.Fprintln(writer, 0)return}if s == 0 {fmt.Fprintln(writer, 1)return}dp := makeGrid(n+1, s+1)dp[1][1] = 1for i := 1; i < n+1; i++ {for j := 1; j < s; j++ {if i < n {dp[i+1][j+1].AddAs(dp[i][j])}if i+j < s+1 {dp[i][i+j].AddAs(dp[i][j])}}}var ans Mintfor i := 0; i < n+1; i++ {ans.AddAs(dp[i][s])}fmt.Fprintln(writer, ans)}func makeGrid(h, w int) [][]Mint {index := make([][]Mint, h, h)data := make([]Mint, h*w, h*w)for i := 0; i < h; i++ {index[i] = data[i*w : (i+1)*w]}return index}// Mod constants.const (Mod1000000007 = 1000000007Mod998244353 = 998244353)var mod Mint = Mod1000000007// Mint treats the modular arithmetictype Mint int64// SetMod sets the mod. It must be called first.func SetMod(newmod Mint) {mod = newmod}// Mod returns m % mod.func (m Mint) Mod() Mint {m %= modif m < 0 {return m + mod}return m}// Inv returns modular multiplicative inversefunc (m Mint) Inv() Mint {return m.Pow(Mint(0).Sub(2))}// Pow returns m^nfunc (m Mint) Pow(n Mint) Mint {p := Mint(1)for n > 0 {if n&1 == 1 {p.MulAs(m)}m.MulAs(m)n >>= 1}return p}// Add returns m+xfunc (m Mint) Add(x Mint) Mint {return (m + x).Mod()}// Sub returns m-xfunc (m Mint) Sub(x Mint) Mint {return (m - x).Mod()}// Mul returns m*xfunc (m Mint) Mul(x Mint) Mint {return (m * x).Mod()}// Div returns m/xfunc (m Mint) Div(x Mint) Mint {return m.Mul(x.Inv())}// AddAs assigns *m + x to *m and returns mfunc (m *Mint) AddAs(x Mint) *Mint {*m = m.Add(x)return m}// SubAs assigns *m - x to *m and returns mfunc (m *Mint) SubAs(x Mint) *Mint {*m = m.Sub(x)return m}// MulAs assigns *m * x to *m and returns mfunc (m *Mint) MulAs(x Mint) *Mint {*m = m.Mul(x)return m}// DivAs assigns *m / x to *m and returns mfunc (m *Mint) DivAs(x Mint) *Mint {*m = m.Div(x)return m}