結果

問題 No.465 PPPPPPPPPPPPPPPPAPPPPPPPP
ユーザー 草苺奶昔草苺奶昔
提出日時 2023-02-20 17:13:22
言語 Go
(1.22.1)
結果
AC  
実行時間 920 ms / 2,000 ms
コード長 5,779 bytes
コンパイル時間 10,533 ms
コンパイル使用メモリ 222,068 KB
実行使用メモリ 266,496 KB
最終ジャッジ日時 2024-07-21 09:09:56
合計ジャッジ時間 20,400 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 31 ms
9,088 KB
testcase_06 AC 144 ms
34,816 KB
testcase_07 AC 34 ms
9,472 KB
testcase_08 AC 150 ms
29,168 KB
testcase_09 AC 385 ms
89,472 KB
testcase_10 AC 433 ms
105,856 KB
testcase_11 AC 920 ms
266,496 KB
testcase_12 AC 629 ms
135,040 KB
testcase_13 AC 466 ms
117,248 KB
testcase_14 AC 517 ms
123,136 KB
testcase_15 AC 674 ms
248,960 KB
testcase_16 AC 577 ms
130,432 KB
testcase_17 AC 621 ms
238,720 KB
testcase_18 AC 674 ms
203,248 KB
testcase_19 AC 612 ms
228,992 KB
testcase_20 AC 152 ms
30,720 KB
testcase_21 AC 637 ms
189,440 KB
32_ratsliveonnoevilstar.txt AC 681 ms
232,704 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import (
	"bufio"
	"fmt"
	"os"
)

const INF int = 1 << 60

func main() {
	// https://yukicoder.me/problems/no/465

	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var s string
	fmt.Fscan(in, &s)
	n := len(s)
	dp1, dp2 := make([]int, n+1), make([]int, n+1)
	buf := make([]int, n+3)
	tree := NewPalindromicTree("")
	for i := 0; i < n; i++ {
		pos := tree.AddChar(s[i])
		if tree.Nodes[pos].Len == i+1 {
			dp1[i+1] = 1
		}

		res := tree.UpdateDp(func(pos, start int) {
			buf[pos] = dp1[start]
		}, func(pos, pre int) {
			buf[pos] += buf[pre]
		})

		for _, p := range res {
			dp2[i+1] += buf[p]
		}
	}

	tree2 := NewPalindromicTree("")
	res, sum := 0, 0
	for i := n - 1; i >= 0; i-- {
		res += dp2[i] * sum
		pos := tree2.AddChar(s[i])
		if tree2.Nodes[pos].Len == n-i {
			sum++
		}
	}
	fmt.Fprintln(out, res)
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

type PalindromicTree struct {
	Chars []byte
	Nodes []*Node
	ptr   int // 新添加一个字母后所形成的最长回文后缀表示的节点
}

type Node struct {
	Len       int          // 结点代表的回文串的长度
	Indexes   []int        // 以哪些索引结尾的最长回文后缀是当前回文串
	Fail      int          // 指向当前回文串的最长回文后缀的位置
	next      map[byte]int // 当前回文串前后都加上字符c形成的回文串
	deltaLink int          // 以当前回文串结尾的长度不同的回文串的位置(ertre -> e)?
}

func NewPalindromicTree(s string) *PalindromicTree {
	res := &PalindromicTree{}
	res.Nodes = append(res.Nodes, res.newNode(0, -1)) // 長さ -1 (奇数)
	res.Nodes = append(res.Nodes, res.newNode(0, 0))  // 長さ 0 (偶数)
	res.AddString(s)
	return res
}

// !添加一个字符,返回以这个字符为后缀的最长回文串的位置pos.
func (pt *PalindromicTree) AddChar(x byte) int {
	pos := len(pt.Chars)
	pt.Chars = append(pt.Chars, x)
	// 如果在这个回文串前后都加上字符c形成的回文串原串的后缀,那么就添加儿子,否则就沿着fail指针往上找
	cur := pt.findPrevPalindrome(pt.ptr)
	_, hasKey := pt.Nodes[cur].next[x]
	if !hasKey {
		pt.Nodes[cur].next[x] = len(pt.Nodes)
	}
	pt.ptr = pt.Nodes[cur].next[x]
	if !hasKey {
		pt.Nodes = append(pt.Nodes, pt.newNode(-1, pt.Nodes[cur].Len+2))
		if pt.Nodes[len(pt.Nodes)-1].Len == 1 {
			pt.Nodes[len(pt.Nodes)-1].Fail = 1
		} else {
			pt.Nodes[len(pt.Nodes)-1].Fail = pt.Nodes[pt.findPrevPalindrome(pt.Nodes[cur].Fail)].next[x]
		}

		if pt.diff(pt.ptr) == pt.diff(pt.Nodes[len(pt.Nodes)-1].Fail) {
			pt.Nodes[len(pt.Nodes)-1].deltaLink = pt.Nodes[pt.Nodes[len(pt.Nodes)-1].Fail].deltaLink
		} else {
			pt.Nodes[len(pt.Nodes)-1].deltaLink = pt.Nodes[len(pt.Nodes)-1].Fail
		}
	}

	pt.Nodes[pt.ptr].Indexes = append(pt.Nodes[pt.ptr].Indexes, pos)
	return pt.ptr
}

func (pt *PalindromicTree) AddString(s string) {
	if len(s) == 0 {
		return
	}
	for i := 0; i < len(s); i++ {
		pt.AddChar(s[i])
	}
}

// 在每次调用AddChar(x)之后使用,更新dp.
//  - init(pos, start): 初始化顶点pos的dp值,对应回文串s[start:].
//  - apply(pos, prePos): 用prePos(fail指针指向的位置)更新pos.
//  返回值: 本次更新的回文串的顶点.
func (pt *PalindromicTree) UpdateDp(init func(int, int), apply func(int, int)) (update []int) {
	i := len(pt.Chars) - 1
	id := pt.ptr
	for pt.Nodes[id].Len > 0 {
		init(id, i+1-pt.Nodes[pt.Nodes[id].deltaLink].Len-pt.diff(id))
		if pt.Nodes[id].deltaLink != pt.Nodes[id].Fail {
			apply(id, pt.Nodes[id].Fail)
		}
		update = append(update, id)
		id = pt.Nodes[id].deltaLink
	}
	return
}

// 求出每个顶点代表的回文串出现的次数.
func (pt *PalindromicTree) GetFrequency() []int {
	res := make([]int, pt.Size())
	for i := pt.Size() - 1; i > 0; i-- {
		res[i] += len(pt.Nodes[i].Indexes)
		res[pt.Nodes[i].Fail] += res[i] // 长回文包含短回文
	}
	return res
}

// 以当前字符结尾的回文串个数.
func (pt *PalindromicTree) CountPalindromes() int {
	res := 0
	for i := 1; i < pt.Size(); i++ {
		res += len(pt.Nodes[i].Indexes)
	}
	return res
}

// 输出每个顶点代表的回文串.
func (pt *PalindromicTree) GetPalindrome(pos int) []string {
	if pos == 0 {
		return []string{"-1"}
	}
	if pos == 1 {
		return []string{"0"}
	}
	res := []byte{}
	pt.outputDfs(0, pos, &res)
	pt.outputDfs(1, pos, &res)
	start := len(res) - 1
	if pt.Nodes[pos].Len&1 == 1 {
		start--
	}
	for i := start; i >= 0; i-- {
		res = append(res, res[i])
	}
	return []string{string(res)}
}

// 回文树中的顶点个数.(包含两个奇偶虚拟顶点)
func (pt *PalindromicTree) Size() int {
	return len(pt.Nodes)
}

// 返回pos位置的回文串顶点.
func (pt *PalindromicTree) GetNode(pos int) *Node {
	return pt.Nodes[pos]
}

// 当前位置的回文串长度减去当前回文串的最长后缀回文串的长度.
func (pt *PalindromicTree) diff(pos int) int {
	if pt.Nodes[pos].Fail <= 0 {
		return -1
	}
	return pt.Nodes[pos].Len - pt.Nodes[pt.Nodes[pos].Fail].Len
}

func (pt *PalindromicTree) newNode(suf, pLen int) *Node {
	return &Node{
		next:      make(map[byte]int),
		Fail:      suf,
		Len:       pLen,
		deltaLink: -1,
	}
}

// 沿着失配指针找到第一个满足 x+s+x 是原串回文后缀的位置.
func (pt *PalindromicTree) findPrevPalindrome(cur int) int {
	pos := len(pt.Chars) - 1
	for {
		rev := pos - 1 - pt.Nodes[cur].Len
		if rev >= 0 && pt.Chars[rev] == pt.Chars[len(pt.Chars)-1] {
			break
		}
		cur = pt.Nodes[cur].Fail
	}
	return cur
}

func (pt *PalindromicTree) outputDfs(v, id int, res *[]byte) bool {
	if v == id {
		return true
	}
	for key, next := range pt.Nodes[v].next {
		if pt.outputDfs(next, id, res) {
			*res = append(*res, key)
			return true
		}
	}
	return false
}
0