結果

問題 No.1671 Permutation Tour
ユーザー ID 21712
提出日時 2026-05-10 13:28:26
言語 Go
(1.26.1)
コンパイル:
env GOCACHE=/tmp go build _filename_
実行:
./Main
結果
AC  
実行時間 1 ms / 2,000 ms
コード長 2,846 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 14,351 ms
コンパイル使用メモリ 278,944 KB
実行使用メモリ 6,400 KB
最終ジャッジ日時 2026-05-10 13:28:45
合計ジャッジ時間 15,370 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

package main

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

var mint = newMint(1e9+7)

func main() {
	var n int
	Scan(&n)
	ans := mint.Div(mint.Mul(mint.Sub(mint.Mul(mint.Nsum(n-1), n), mint.N2sum(n-1)), 2), n-1)
	Println(mint.Wrap(ans))
}

/*
考察

|Qi-Qj|の値Dごとに和sum[D]を求めると

D=1
sum[1] = |2-1|+|3-2|+|4-3|+ ... + |(N-1)-(N-2)|+|N-(N-1)| = 1 * (N-1)

D=2
sum[2] = |3-1|+|4-2|+|5-3|+ ... + |(N-1)-(N-3)|+|N-(N-2)| = 2 * (N-2)

D=3
sum[3] = |4-1|+|5-2|+|6-3|+ ... + |(N-1)-(N-4)|+|N-(N-3)| = 3 * (N-3)
...

D=N-3
sum[N-3] = |(N-2)-1|+|(N-1)-2|+|N-3| = (N-3) * 3 = (N-3) * (N - (N-3))

D=N-2
sum[N-2] = |(N-1)-1|+|N-2| = (N-2) * 2 =  (N-2) * (N - (N-2))

D=N-1
sum[N-1] = |N-1| = (N-1) * 1 = (N-1) * (N - (N-1))

規則性があるぽく見えるので
D=1..(N-1)
sum[1..(N-1)] = 1*(N-1) + 2*(N-2) + ... + (N-1)*(N-(N-1))
             = (1 + 2 + ... + (N-1))*N - (1*1 + 2*2 + ... + (N-1)*(N-1))
             = Nsum(N-1)*N - N2sum(N-1)
(※ Nsum(N) ... 1～Nまでの総和)
(※ N2sum(N) ... 1～Nまでの二乗和)

例えば周遊コストの計算式に (8,3) の組み(|8-3|または|3-8|)が発生するのは 2*N*(N-2)! 通り

なので答えは
ANSWER = sum[1..(N-1)] * 2*N*(N-2)! / N!
       = sum[1..(N-1)] * 2 / (N-1)
       = (Nsum(N-1)*N - N2sum(N-1)) * 2 / (N-1)
       
*/


type Mint struct {
	Mod int
	ModInt *Int
	invCache map[int]int
}

func newMint(mod int) *Mint {
	return &Mint{
		Mod: mod,
		ModInt: NewInt(int64(mod)),
		invCache: make(map[int]int),
	}
}

func (mint *Mint)wrap(a int) int {
	return a%mint.Mod
}

func (mint *Mint)Wrap(a int) int {
	return mint.add(mint.wrap(a),mint.Mod)
}

func (mint *Mint)add(a, b int) int {
	return mint.wrap(a+b)
}

func (mint *Mint)Add(a int, bs ...int) int {
	a = mint.wrap(a)
	for _, b := range bs {
		a = mint.add(a, mint.wrap(b))
	}
	return a
}

func (mint *Mint)sub(a, b int) int {
	return mint.wrap(a-b)
}

func (mint *Mint)Sub(a int, bs ...int) int {
	a = mint.wrap(a)
	for _, b := range bs {
		a = mint.sub(a, mint.wrap(b))
	}
	return a
}

func (mint *Mint)mul(a, b int) int {
	return mint.wrap(a*b)
}

func (mint *Mint)Mul(a int, bs ...int) int {
	a = mint.wrap(a)
	for _, b := range bs {
		a = mint.mul(a, mint.wrap(b))
	}
	return a
}

func (mint *Mint)inv(a int) int {
	if v, ok := mint.invCache[a]; ok {
		return v
	}
	x := int(new(Int).ModInverse(NewInt(int64(a)), mint.ModInt).Int64())
	mint.invCache[a] = x
	return x
}

func (mint *Mint)Inv(a int) int {
	return mint.inv(mint.wrap(a))
}

func (mint *Mint)div(a, b int) int {
	return mint.wrap(a*mint.inv(b))
}

func (mint *Mint)Div(a int, bs ...int) int {
	a = mint.wrap(a)
	for _, b := range bs {
		a = mint.div(a, mint.wrap(b))
	}
	return a
}

func (mint *Mint)Nsum(n int) int {
	return mint.Div(mint.Mul(n, n+1), 2)
}

func (mint *Mint)N2sum(n int) int {
	return mint.Div(mint.Mul(n, n+1, 2*n+1), 6)
}
0