結果

問題 No.1127 変形パスカルの三角形
ユーザー ID 21712
提出日時 2026-06-07 17:57:11
言語 Go
(1.26.1)
コンパイル:
env GOCACHE=/tmp go build _filename_
実行:
./Main
結果
AC  
実行時間 7 ms / 1,500 ms
コード長 2,116 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 16,201 ms
コンパイル使用メモリ 275,568 KB
実行使用メモリ 6,400 KB
最終ジャッジ日時 2026-06-07 17:57:32
合計ジャッジ時間 17,804 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_0
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

package main

import . "fmt"
import . "math/big"

const M = 1e9+7

func main() {
	var a,b,n,k int
	Scan(&a,&b,&n,&k)
	
	a %= M
	b %= M
	
	const Z int = 2e5
	
	xs := make([]int, Z+1)
	xs[0] = 1
	for i := 1; i < len(xs); i++ {
		xs[i] = xs[i-1]*i%M
	}
	ys := make([]int, len(xs))
	ys[Z] = int(new(Int).ModInverse(NewInt(int64(xs[Z])), NewInt(M)).Int64())
	for i := Z; i > 0; i-- {
		ys[i-1] = ys[i]*i%M
	}
	
	ans1 := (xs[n-1]*ys[k-1]%M*ys[(n-1)-(k-1)]%M*a%M + xs[n-1]*ys[k-2]%M*ys[(n-1)-(k-2)]%M*b%M)%M
	Println(ans1)
	
	ans2 := 0
	tb := 0
	for i := 0; i < n; i++ {
		t := xs[n-1]*ys[i]%M*ys[(n-1)-i]%M
		e := (t*a%M+tb)%M
		tb = t*b%M
		ans2 = (ans2+e*e%M)%M
	}
	ans2 = (ans2+tb*tb%M)%M
	Println(ans2)
}

/*
考察

よくわからない

サンプル1を描いてみる
a=1, b=1
    1  2  3  4  5  6
1)  1  1
2)  1  2  1
3)  1  3  3  1
4)  1  4  6  4  1
5)  1  5 10 10  5  1

a=3,b=8 を描いてみる
    1  2  3  4  5  6
1)  3  8
2)  3 11  8
3)  3 14 19  8
4)  3 17 33 27  8
5)  3 20 50 60 35  8

一般化

1)  a  b
2)  a (a+b) b
3)  a (a+(a+b)) ((a+b)+b) b
4)  a (a+(a+(a+b))) ((a+(a+b))+((a+b)+b)) (((a+b)+b)+b) b
5)  a (a+(a+(a+(a+b)))) ((a+(a+(a+b)))+((a+(a+b))+((a+b)+b))) (((a+(a+b))+((a+b)+b))+(((a+b)+b)+b)) ((((a+b)+b)+b)+b) b

整理
1)  a b
2)  a (a+b) b
3)  a (2a+b) (a+2b) b
4)  a (3a+b) (3a+3b) (a+3b) b
5)  a (4a+b) (6a+4b) (4a+6b) (a+4b) b
6)  a (5a+b) (10a+5b) (10a+10b) (5a+10b) (a+5b) b
7)  a (6a+b) (15a+6b) (20a+15b) (15a+20b) (6a+15b) (a+6b) b
例えば 7段目
    a  6a     15a      20a       15a       6a       a
          b       6b       15b       20b      15b     6b  b
aとbそれぞれ左右対称の係数同じなのを1個ずつずらして重ねている感じ
係数はいわゆる二項係数？
二項係数を並べたやつをパスカルの三角形と呼ぶらしい
パスカルの三角形をa倍したものとb倍したものを1個ずつずらして並べたということか

二項係数(n,k)を求めa倍とb倍すればいいのかな
(n,k) = n! / (k! * (n-k)!)

二乗和は二乗して足すをやるのみ…


nの最大は2e5なので計算間に合う

*/
0