結果
| 問題 | 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()
}
            
            
            
        