T1 找一找

统计一下 1110000001000000 的数字分别有多少个。对于每个数字,看看原来的集合中有没有他的倍数,若有就更新答案。复杂度 O(nlogn)O(nlogn)

T2 数一数

假如一个字符串的长度不是所有字符串中最短的,那么其答案一定为 00,因为它在最短的字符串中没有出现过。找出任意一个长度最短的字符串,用 kmpkmp 算法把它和每个串进行匹配,求出它在每个串中出现了多少次,乘起来就是答案。所有长度最短的字符串答案都相同,不需要重复匹配。

T3 列一列

选择一些素数,计算输入的数模这些素数的值,再一个一个计算斐波那契数列的每一项模这些素数的值,直到找到第一个完全一样的就是答案。

T4 造一造

要求第 mm 个元素入栈后栈中恰有 kk 个元素,也就是在此之前出栈过 mkm- k 个元素。所以在这个共计2n2 n 次操作中,第2mk2 m-k 个操作是入栈。
而前面有 m1 m - 1 次入栈和mkm -k 次出栈,后面有nmn -m 次入栈和 nm+k n-m+k 次出栈,则可以两边先分别计算。而求nn次入栈mm次出栈的合法排列次数则可参考卡特兰数公式,C(n+m,n)C(n+m,m1) C(n+m,n)-C(n+m,m-1)

T5 组一组

对于每一位分开考虑 问题简化如下: 有一个长为n n0101串,记Sum[]Sum[]为前缀和,有四种限制:

1、对于[l,r][l,r]按位与和为xx,且xx的当前位为11,则区间[l,r][l,r]全为11

(Sum[r]Sum[l1]==rl+1) (Sum[r] - Sum[l - 1] == r - l + 1)

2、对于[l,r][l,r]按位或和为xx,且xx的当前位为00,则区间[l,r][l,r]全为00

(Sum[r]Sum[l1]==0)(Sum[r] - Sum[l - 1] == 0)

3、对于[l,r][l,r]按位或和为xx,且xx的当前位为11,则区间[l,r][l,r]存在11

(Sum[r]>=Sum[l1]+1)(Sum[r] >= Sum[l - 1] + 1)

4、对于[l,r][l,r]按位与和为xx,且xx的当前位为00,则区间[l,r][l,r]存在00

(Sum[r]<=Sum[l1]+rl)(Sum[r] <= Sum[l - 1] + r - l)

这个可以用差分约束系统 +最短路来求一组解,由于题目保证有解,所以不用判负环,即无解的情况。

T6导一导

先考虑只有一项的情况

那么可以把求导理解成你每一轮选择两种操作中的一种,要么是把自己从变成,并且当前权值乘上,要么分母上从变成,并且当前权值乘上i,ni,n阶导就是所有操作的和。

那么易知求n阶导对的贡献为对的贡献形式也类似,都是可以用fft来求的。

所以时间复杂度O((n+k)log(n+k)) O((n+k)log(n+k))