No Abstract.

T1

Des.

$\sum_{i=1}^{n}\sum_{j=1}^{i}{S_{i,j}D_jP_j}.$

类似[HEOI2016]求和, 列出第二类斯特林数列上的和式, 发现可以卷积.

错位排列数和圆排列数都可以$O(n)$递推.

1
2

定义一个优秀的序列, 有:

$\text{for }i\text{ in }1 \ldots n-1, {a_i \choose a_{i+1}}\text{ is odd.}$

给一个序列, 求优秀的子序列数. BZOJ 4903

根据Lucas定理有, 后面的数一定是前一个数的子集. 我们从后向前DP. 设状态$f_{i,j}$, 高9位为$i$的子集, 低9位为$j$的方案数.

每次取出当前数低9位所有子集的方案数, 加上只取这个数自己的方案, 贡献到高9位的所有超集中去.

最后答案减去所有只取一个数的方案.

为什么能想到这样DP?

1
2

每次询问一个区间, 问区间连乘积的$\varphi \mod{998244353}$.

把询问离线.

由于$\varphi$对每个素因子只取一次, 所以我们预处理一下每个素因子上一次出现的位置和下一次出现的位置. 离开一个位置时, 去掉这个位置的贡献并在下一次出现处贡献一下. 进入一个位置时, 仅当在此之前没有出现过时, 素因子可以贡献.

树状数组维护前缀积. 还有一个在线的主席树版本BZOJ 4026.

主席树维护区间积, 令每个素因子只在最右边的版本中贡献, 查询$[l,r]$时在版本$r$查询区间积即可.

1
2