A: Blank
题意
有 $n (n \leq 100)$ 个格子,向其中填入 $0、1、2、3 $这$4$个数,但是有 $m ( m ≤ 100)$ 个限制
限制 $l$ $ r$ $x$ :表示 $l ~ r$ 的格子内不同的数的个数为$x$
要求满足所有限制的方案有多少种?
思路
我们首先设$dp[i][j][k][r]$为这$0,1,2,3$四个数字的最后一次出现的位置,$dp$值为方案数
那么转移可以这样写一下:
$dp[cur][j][k][r] += dp[i][j][k][r], dp[i][cur][k][r] += dp[i][j][k][r]$
$dp[i][j][cur][r] += dp[i][j][k][r], dp[i][j][k][cur] += dp[i][j][k][r]$
因为$i,j,k,r$互不相同, 且当位一定为一个数字并且相互之间有大小顺序,那么我们把$dp$按照大小来转移的话
还是$dp[cur][i][j][k]$ 其中$cur \geq i \geq j \geq k$
那么转移就变成
$dp[cur+1][i][j][k]+=dp[cur][i][j][k], dp[cur+1][cur][j][k] += dp[cur][i][j][k]$
$dp[cur+1][cur][i][k] += dp[cur][i][j][k], dp[cur+1][cur][i][j] += dp[cur][i][j]$
我们不必要区分$0,1,2,3$对应的是哪一个,因为这对结果没影响
这样的$dp$数组太大,我们可以用滚动数组来优化一下空间
AC代码
实测$dp$数组降序会$T$,可能是因为$dp$过程中地址变换太大造成超时.
1 |
|
L: Sequence
题意
给一个长度为n的数组,有m次操作,操作有3种,给一个x,每次改变序列的值$bi=\sum\limits{j=i-k*x}a_j$
求改变完了的序列的$(i\times a[i])$值的异或和
思路
通过打表观察可以发现,一种操作多次操作就是把序列$a$和组合数序列进行卷积,然后就直接用ntt就行了
AC代码
1 |
|