首页 > 游游的9的倍数
开通博客写题解
头像 起名字真难233
发表于 2023-07-02 23:30:25
一般来说，要求符合条件的子序列的数量，而且子序列是不连续的（虽然子序***实都是不连续的）都可以考虑dp来做，一般的思路就是考虑从0~k号位置的子序列个数与0~k-1号位置的子序列个数之间的关系，找到状态转移方程 这题要找的是9倍，一般来说，如果0~k位子序列的和是9的倍数，第k位我们 展开全文
去ta的博客 赞 (14) 回复(0) 收起
头像 以诚丶
发表于 2025-07-17 18:00:08
关于这种比较小的模数计数，一般可以给dp多加一个状态，也就是当前的数模特定值之后为多少。 对于本题，我们可以定义定义代表了从前位中选出的数模后值为，那么有如下状态转移方程： 情况1，不选当前数: 情况2，选当前数: ，其中是第位数的值。 其中basecase为，其他. 需要特别注意的是，空 展开全文
去ta的博客 赞 (1) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”