[Codeforces 755G]Chocolate

Description

$n$个球排成一列,定义一组球为一个球或相邻的两个球。每个球最多属于一组球。给出$k$,要求对于$1\le m\le k$的每个$m$,求出从序列中恰好选出$m$组球的方案数。答案对$998244353$取模。
继续阅读 [Codeforces 755G]Chocolate

1+

【DEF题十连测A】[Codeforces 895D]String Mark

Description

给出等长的$AB$串,问有多少$A$串的重排列得到的串字典序大于$A$串,小于$B$串。
继续阅读 【DEF题十连测A】[Codeforces 895D]String Mark

3+

[BZOJ4671]异或图

Description

定义两个结点数相同的图$G_1$与图$G_2 $的异或为一个新的图$G$, 其中如果$(u, v) $在$G_1$与$G_2$中的出现次数之和为$1$, 那么边$(u, v)$在$G$中, 否则这条边不在$G$中.

现在给定$s $个结点数相同的图$G_{1 \sim s}$, 设$S = \{G_1, G_2, \cdots , G_s\}$, 请问$S$有多少个子集的异或为一个连通图?

第一行为一个整数$s$, 表图的个数.

接下来每一个二进制串, 第$i$行的二进制串为$g_i$,其中$g_i$是原图通过以下伪代码转化得到的. 图的结点从$1$开始编号, 下面设结点数为$1$.


继续阅读 [BZOJ4671]异或图

0

[ECUSTOJ#4]果实计数

Description

淘淘家有棵奇怪的苹果树,这棵树共有$n+1$层,标号为$0 \sim n$。这棵树第$0$层只有一个节点,为根节点。已知这棵树为$b$叉树,且保证是一颗满$b$叉树。
现在,该树第$n$层的每个节点上都结出了一个苹果,淘淘想知道共结了多少苹果。由于数量可能很大,答案要求输出$\bmod\ k$后的结果。
继续阅读 [ECUSTOJ#4]果实计数

0

[ECUSTOJ#45]不等数列

Description

将$1$到$n$任意排列,然后在排列的每两个数之间根据他们的大小关系插入$>$和$<$。

问在所有排列中,有多少个排列恰好有$k$个$<$。答案对$2012$取模。 例如:排列$1~4~3~2~5$,插入$>$和$<$后变成:$1 < 4 > 3 > 2 < 5$

多组数据,$1 \leq n \leq 1000,0 \leq k < n$
继续阅读 [ECUSTOJ#45]不等数列

0

[ECUSTOJ#21]幂之和

Description

对于正整数$k$,可以定义$k$次方和
$$S _ { k } ( n ) = \sum _ { i = 1 } ^ { n } i ^ { k }$$
可以把它写成下面的形式,当$M$取最大可能的正整数时,所有的系数$a_i$都是确定的:
$$S _ { k } ( n ) = \frac { 1 } { M } \left( a _ { k + 1 } n ^ { k + 1 } + a _ { k } n ^ { k } + \ldots + a _ { 1 } n + a _ { 0 } \right)$$

现在给定整数$k$,输出$M , a _ { k + 1 } , a _ { k } , \dots , a _ { 1 } , a _ { 0 }$。$k \leq 20$

Solution

当然是Mathematica打表

表有点长,这里就不打了
这题的正解应该是拉格朗日插值
弄$k+1$个值出来然后带进去就ok
代码懒得敲了。。

0

[Codeforces 161E]Tetrahedron

Problem

一个正四面体顶点为$A,B,C,D$,从$D$出发,每走一步,更变当前所在顶点(不能保持不变),给定一个数$n$,求能有几种不同路径使得第$n$步走到$ D$。$1 \leq n \leq 10^7$

Solution

Method 1

当然是考虑递推辣
分两种情况:

  1. 第$ n-2 $步不在$ D$
  2. 第$ n-2 $步在$ D$

设$ a[n] $是第$ n $步到达$ D$的不同路径数。
对于 1 情况:第$ n-2 $步在$A,B,C$当中的一点,那么这时,在第$ n-1 $步能够到达$ D$,但其实他可以选择在第$ n-1 $到达另外两点,然后在第$ n $步到达$ D$,所以这种情况有$ 2a[n-1] $种。
对于 2 情况:第$ n-2 $步在$ D$点,那么他可以通过走到$A,B,C$中的任意一点,再回到$D$点,所以这种情况有$ 3a[n-2] $种。
故有$a[n]=2a[n-1]+3a[n-2]$

Method 2

特征方程!
优化至$O (\log n)$
Code:


通项公式:$a _ { n } = \frac { 3 } { 4 } \left( 3 ^ { n – 1 } – ( – 1 ) ^ { n – 1 } \right) ( n > 1 )$

Method 3

用$ dp[i][j] $表示第$ i $步走到$ j $点,则有:
$$dp[i][j]=dp[i][j]+dp[i-1][k]~~(j\ne{k})$$
于是从遍历$i,j,k$,最后取$ dp[n][3] $即可

Method 4

走$ n $步的总共不同路径有$3^{n}$条,若算出第$ n $点到达$ D $的概率,最后乘上$3^{n}$再取模即可。设$P_{n}(A)$为第$ n $步到达$A $点的概率,那么由对称性可知:$P_{n}(A)+P_{n}(B)+P_{n}(C)+P_{n}(D)=1$
又知$A,B,C$三点完全等价,故有$P_{n}(A)=P_{n}(B)=P_{n}(C)=\frac{1-P_{n}(D)}{3}$
然后又可知第$ n-1 $步必定在$A,B,C$当中一点,且无论在哪一点总有$\frac{1}{3} $的概率走到$D$,故有:
$$P_{n+1}(D)=\frac{1}{3}(P_{n}(A)+P_{n}(B)+P_{n}(C))=\frac{1-P_{n}(D)}{3}$$
结合$P_{1}(D)=0$可算出$P_{n}(D)$的表达式为:$3^{n}P_{n}(D)=\frac{3}{4}(3^{n-1}-(-1)^{n-1})$
跟递推的通项公式相同。

3+