結果
問題 |
No.1460 Max of Min
|
ユーザー |
|
提出日時 | 2025-10-08 17:45:56 |
言語 | Go (1.23.4) |
結果 |
AC
|
実行時間 | 791 ms / 2,000 ms |
コード長 | 3,235 bytes |
コンパイル時間 | 20,117 ms |
コンパイル使用メモリ | 250,876 KB |
実行使用メモリ | 8,312 KB |
最終ジャッジ日時 | 2025-10-08 17:46:44 |
合計ジャッジ時間 | 35,390 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 91 |
ソースコード
// 半环上的线性递推 // O(n^2logk) // https://nyaannyaan.github.io/library/verify/verify-yuki/yuki-1460.test.cpp package main import ( "bufio" "fmt" "os" "slices" ) // Semiring type AddFunc[T any] func(a, b T) T type MulFunc[T any] func(a, b T) T type IdFunc[T any] func() T type LinearRecursive[T any] struct { C []T // 递推系数 c_1, c_2, ... N int // 递推阶数 Add AddFunc[T] // 半环加法 Mul MulFunc[T] // 半环乘法 Id0 IdFunc[T] // 加法单位元 Id1 IdFunc[T] // 乘法单位元 } func NewLinearRecursive[T any]( c []T, add AddFunc[T], mul MulFunc[T], id0, id1 IdFunc[T], ) *LinearRecursive[T] { cc := slices.Clone(c) return &LinearRecursive[T]{ C: cc, N: len(cc), Add: add, Mul: mul, Id0: id0, Id1: id1, } } // KthTerm 计算递推关系的第 k 项 // a 是初始项 a_0, a_1, ..., a_{N-1} func (lr *LinearRecursive[T]) KthTerm(a []T, k int) T { if len(a) != lr.N { panic("len(a) != len(C)") } if k < len(a) { return a[k] } coeff := lr.getCoeff(k) res := lr.Id0() for i := range lr.N { res = lr.Add(res, lr.Mul(a[i], coeff[lr.N-1-i])) } return res } func (lr *LinearRecursive[T]) getCoeff(k int) []T { if k == 0 { b := make([]T, lr.N) for i := range b { b[i] = lr.Id0() } b[lr.N-1] = lr.Id1() return b } half := lr.getCoeff(k / 2) half = lr.doubling(half) if (k & 1) == 1 { half = lr.increment(half) } return half } func (lr *LinearRecursive[T]) increment(b []T) []T { v := make([]T, lr.N) for i := 0; i+1 < lr.N; i++ { v[i] = b[i+1] } v[lr.N-1] = lr.Id0() t := b[0] for i := range lr.N { v[i] = lr.Add(v[i], lr.Mul(t, lr.C[i])) } return v } func (lr *LinearRecursive[T]) doubling(b []T) []T { v := make([]T, lr.N) for i := range lr.N { v[i] = lr.Id0() } bb := slices.Clone(b) for i := range lr.N { mul := b[lr.N-1-i] for j := range lr.N { v[j] = lr.Add(v[j], lr.Mul(bb[j], mul)) } bb = lr.increment(bb) } return v } func fib() { // 示例:斐波那契数列 // a_n = 1*a_{n-1} + 1*a_{n-2} // C = {1, 1} (c_1, c_2) // a = {0, 1} (a_0, a_1) add := func(a, b int) int { return a + b } mul := func(a, b int) int { return a * b } id0 := func() int { return 0 } id1 := func() int { return 1 } lr := NewLinearRecursive([]int{1, 1}, add, mul, id0, id1) a := []int{0, 1} fmt.Println("Calculating Fibonacci numbers:") for k := range 10 { fmt.Printf("F(%d) = %d\n", k, lr.KthTerm(a, k)) } fmt.Printf("F(30) = %d\n", lr.KthTerm(a, 30)) // 应该输出 832040 } func yuki1460() { in := bufio.NewReader(os.Stdin) out := bufio.NewWriter(os.Stdout) defer out.Flush() const INF int = 2e18 var k, n int fmt.Fscan(in, &k, &n) a := make([]int, k) b := make([]int, k) for i := range k { fmt.Fscan(in, &a[i]) } for i := range k { fmt.Fscan(in, &b[i]) } for i, j := 0, k-1; i < j; i, j = i+1, j-1 { b[i], b[j] = b[j], b[i] } add := func(a, b int) int { if a > b { return a } return b } mul := func(a, b int) int { if a < b { return a } return b } id0 := func() int { return -INF } id1 := func() int { return INF } lr := NewLinearRecursive(b, add, mul, id0, id1) fmt.Fprintln(out, lr.KthTerm(a, n)) } func main() { yuki1460() }