求助

学术版

xiaomiao_001 @ 2024-11-29 14:31:12

有一个只含有4种字母的字符串，求四个字母出现次数相同的字串数量，n在5000以内

by Harlem @ 2024-11-29 14:37:27

口胡线段树O(n^2logn)，但不知道，有可能是假的QwQ

by Harlem @ 2024-11-29 14:40:27

@xiaomiao_001

听说回复完应该 @ 一下QwQ

by xyz105 @ 2024-11-29 14:51:23

@xiaomiao_001 预处理四种字母的个数的前缀和，O(n^2) 暴力枚举所有区间即可。

by ZMQ_Ink6556 @ 2024-11-29 14:51:31

@xiaomiao_001 若 n \mod 4 \neq 0，无解。否则排列组合求解

by xyz105 @ 2024-11-29 14:51:47

@Harlem 用线段树是不是有点过分了。

by xiaomiao_001 @ 2024-11-29 14:54:56

@ZMQ_Ink6556@xyz105@Harlem 谢谢QWQ

by Fu_Xuan @ 2024-11-29 15:02:11

差分一下，用map维护，然后组合数乱搞

|