标签：动态规划

【Codeforces 1681E】Non-Intersecting Subpermutations

题目描述给定 $n, k$，求由 $[1,k]$ 组成所有长度为 $n$ 的序列的贡献之和，一个序列的贡献为能够在其中找到的最多互不交叉的段数使得每一段长度为 $k$ 且恰好包含 $[1,k]$ 中每个数，输出答案对 $998244353$ 取模的值。 $2\le n,k\le 4000$。 ......

Posted by WHZ0325 on 2023-09-05

【CF 1798F】Gifts from Grandfather Ahmed

题目描述有 $n+1$ 个数 ${a_i}$，分成 $k$ 组，其中第 $i$ 组分得的数之和必须为 $s_i$ 的倍数，保证 $\sum s_i=n+1$，第 $n+1$ 个数丢失，要给出任一满足条件的 $a_{n+1}$ 的值和分组方案。 $1\le n,k\le 200$，$1\le a......

Posted by WHZ0325 on 2023-03-29

【CF 1798E】Multitest Generator

题目描述定义一个序列为 test 仅当序列的第一个元素为这个序列剩下元素的长度。定义一个序列为 multitest 仅当该序列的第一个数为能够将剩下元素组成的序列拆成的 test 的个数。定义一次修改操作可以将序列中任意元素修改为任意一个非负整数。定义函数 $f(A)$ 为将序列修改为 ......

Posted by WHZ0325 on 2023-03-28

【SHOI 2015】超能粒子炮·改

题目描述有 $t$ 组数据，每组数据给定 $n,k$，求 $\sum_{i=0}^kC_n^i\mod 2333$ 的值。 $t\le 100000$，$n,k\le 10^{18}$。算法分析感觉可能是套路题…… 设 $f[n][k]=\sum_{i=0}^kC_n^i\mod 2333$......

Posted by WHZ0325 on 2019-05-01

【CTSC 2017】吉夫特

题目描述给定一个长度为 $n$ 的序列 $A$，求有多少个子序列满足所选下标集合为 ${b_1,b_2,\dots,b_k}$ 时 $a_{b_1}\ge a_{b_2}\ge\dots\ge a_{b_{k-1}}\ge a_{b_k}$ 且 $\prod_{i=2}^kC_{a_{i-1}......

Posted by WHZ0325 on 2019-04-28

【AHOI 2008】逆序对

题目描述给定一个由 $[1,k]$ 之间的数字组成的长度为 $n$ 序列，其中有一些位置上的数不可见，标记为 $-1$，求这个序列的最少逆序对数。 $n\le 10000$，$k\le 100$。算法分析首先需要发现一个结论：要使逆序对数最少，从前到后依次填写的不可见的数字一定单调不下降。 ......

Posted by WHZ0325 on 2019-03-24

【CF 981D】Bookshelves

题目描述给定一个长度为 $n$ 的数列 $a_i$，将其划分为 $k$ 个连续的子段，每一段和相与的值最大是多少。 $1\le k\le n\le 50$，$0\lt a_i\le 2^{50}$。算法分析看到相与的值最大，考虑按位贪心，定义 $f_{i,j}$ 表示将前 $i$ 个数划分为......

Posted by WHZ0325 on 2019-03-23

【ZJOI 2012】波浪

题目描述由 $[1,n]$ 组成的排列，求其波动强度大于 $m$ 的概率，结果保留 $k$ 位小数。定义波动强度为每个数与其相邻数的差的绝对值之和。 $n\le 100$，$k\le 30$，$m\le 2147483647$。算法分析求波度强度大于 $m$ 的概率，我们可以求出每个波度强度......

Posted by WHZ0325 on 2019-03-23