idea

未分类

12.1
后缀树把我写恶心了QAQ

来个出题的idea刺激一下我悲伤的心灵

1

给出原串任意个匹配串，总和不超过10^5，求满足$[l,r]$中匹配串出现恰好$k$次的$l$和$r$的个数

什么发现只能k很小的时候线段树暴力合并= =
怎么随手一道垃圾题，难受

12.10

翻之前的pdf看到的一道题给了我一点idea

2

每个人有$a_i$ 个礼物，每个人会把自己的礼物送给一些人，但自己至多收到一个礼物，且必须收到一个礼物 $\sum a_{i} >= n$
求方案数

题解：
太水了
只要随手容斥一下就好了
至少有0个人收到自己的礼物-至少有1个人收到自己的礼物+至少有2个收到自己的礼物，

3

$\sum_{i_{1} = 1}^{N} \sum_{i_{2} = 1}^{N} \sum_{i_{3} = 1}^{N} \cdots \sum_{i_{k} = 1}^{N} \mu(lcm(i_{1},i_{2},i_{3}\cdots i_{k}))^2$
好像单次方系数的我推错了
二次方只要统计一下N以内质数的指数幂不超过1的数，的k次幂

4

做AtCoder来的灵感
给定一个$k$维空间，每维的大小是$a_i$，我现在要往里面填$\prod_{i = 1}^{k} a_{i}$个数，给定某一维某个位置的最大值，求方案数
填的数总和在50000000以内

一维就直接乘个阶乘
二维的就统计一下当前能用的列数和行数，减去比它大的数的个数，如果这个数被固定在某一维上，就乘上他所有能用的位置
更高维的扩展很简单
保证$n <= 1000000$
复杂度$n^k + nk$显然复杂度瓶颈在前面