T1 找一找
统计一下 到 的数字分别有多少个。对于每个数字,看看原来的集合中有没有他的倍数,若有就更新答案。复杂度 。
T2 数一数
假如一个字符串的长度不是所有字符串中最短的,那么其答案一定为 ,因为它在最短的字符串中没有出现过。找出任意一个长度最短的字符串,用 算法把它和每个串进行匹配,求出它在每个串中出现了多少次,乘起来就是答案。所有长度最短的字符串答案都相同,不需要重复匹配。
T3 列一列
选择一些素数,计算输入的数模这些素数的值,再一个一个计算斐波那契数列的每一项模这些素数的值,直到找到第一个完全一样的就是答案。
T4 造一造
要求第 个元素入栈后栈中恰有 个元素,也就是在此之前出栈过 个元素。所以在这个共计 次操作中,第 个操作是入栈。
而前面有 次入栈和次出栈,后面有次入栈和 次出栈,则可以两边先分别计算。而求次入栈次出栈的合法排列次数则可参考卡特兰数公式, 。
T5 组一组
对于每一位分开考虑 问题简化如下: 有一个长为的串,记为前缀和,有四种限制:
1、对于按位与和为,且的当前位为,则区间全为
2、对于按位或和为,且的当前位为,则区间全为
3、对于按位或和为,且的当前位为,则区间存在
4、对于按位与和为,且的当前位为,则区间存在
这个可以用差分约束系统 +最短路来求一组解,由于题目保证有解,所以不用判负环,即无解的情况。
T6导一导
先考虑只有一项的情况
那么可以把求导理解成你每一轮选择两种操作中的一种,要么是把自己从变成,并且当前权值乘上,要么分母上从变成,并且当前权值乘上阶导就是所有操作的和。
那么易知求n阶导对的贡献为对的贡献形式也类似,都是可以用fft来求的。
所以时间复杂度。