「LOJ 6183」看无可看

Description

有一个数列$f$,对$\forall i\geq2,f_i=2f_{i-1}+3f_{i-2}$,给定$f_0=1,f_1=1$,再给定一个集合$S=\{a_{1},\cdots,a_{ n}\}$和$k$,求$\begin{align*}\sum\limits_{\substack{S'\subset S\\|S'|=k}}f\left(\sum\limits_{x\in S'}x\right)\end{align*}$
$n,k\leqslant 10^5$


- 阅读全文 -

「HDU 5659」CA Loves Substring

Description

给出一个由$0..9$构成的长度为$n$的字符串$s$,$f[i]$表示$s$从$i$断开后(即$s[1.. n]$分成$s[1.. i]$和$s[i+1.. n]$两个串),两个串中本质不同的串的个数(例如一个不同的子串$a$在两个串出现的总次数为$\rm cnt$,$\rm cnt>1$则对$f[i]+1$)。
输出$\displaystyle \sum_{j=1}^{n-1}f[j] \times 100013^{n-j-1}\mod(10^9+7)$
$n \leqslant 2\times 10^5$



- 阅读全文 -

「BZOJ 3998」[TJOI2015]弦论

Description

对于一个给定长度为$N$的字符串,求它的第$K$小子串是什么。
$N \leqslant 5 \times 10^5, \ T<2, \ K \leqslant 10^9$


- 阅读全文 -

「BZOJ 4818」[SDOI2017]序列计数

Description

Alice想要得到一个长度为$n$的序列,序列中的数都是不超过$m$的正整数,而且这$n$个数的和是$p$的倍数。
Alice还希望,这$n$个数中,至少有一个数是质数。
Alice想知道,有多少个序列满足她的要求。
$1 \leq n \leq 10^{9}, 1 \leq m \leq 2 \times 10^{7}, 1 \leq p \leq 100$




- 阅读全文 -

何为pairwise disjoint

Set of Sets

A set of sets $S$ is said to be pairwise disjoint if and only if:

$$ \forall X, Y \in \Bbb S: X \ne Y \implies X \cap Y = \varnothing $$

Here, $∩$ denotes intersection, and $\varnothing$ denotes the empty set.

Hence we can say that the elements of $S$ are pairwise disjoint.

Family of Sets

An indexed family of sets $\left \langle {S_i} \right \rangle_{i \mathop \in I}$ is said to be pairwise disjoint if and only if:

$$ \forall i, j \in I: i \ne j \implies S_i \cap S_j = \varnothing $$

Hence the indexed sets $S_i$ themselves, where $i\in I$, are referred to as being pairwise disjoint.