首页 > 数学考试
开通博客写题解
头像 范艺杰
发表于 2020-10-10 00:03:12
我们发现可以通过第一个不合法的位置不重不漏的统计所有非法方案。设dp[i]表示处理到sa[i],且sa[1]，sa[2]...sa[i - 1]这些点都是合法的方案数。那么答案就是n! - dp[1] * (n - sa[1])! - dp[2] * (n - sa[2])! - ... - dp[ 展开全文
去ta的博客 赞 (10) 回复(0) 收起
头像 __故人__
发表于 2020-10-10 08:52:55
分析 我们可以假象一个假的限制 记录前 个条件都满足，但第 个条件不满足的方案数，考虑 之间的数随便排列， ，然后第 个条件不满足，前 个条件都满足，乘 ；对于不同的 ，方案是不相交的，且 计算了所有不应该在 中计数到的方案数所以 。思路来源与不知名的大佬。我这里只是分享一下做法 展开全文
去ta的博客 赞 (9) 回复(0) 收起
头像 ☆北极星☆
发表于 2020-10-10 22:07:38
首先我们要明白dp[i]表示的是什么，看了好久的别人的代码才看懂了(i am vegetable),dp[i]表示的是长度为p[i]，满足前i-1个限制条件的合法子串的个数！（看不懂就看例子）举个例子，此时的限制条件有3个，分别是p[1]=3,p[2]=5,p[3]=7,那么dp[1]就是表示满足前 展开全文
去ta的博客 赞 (4) 回复(1) 收起
头像 lemondinosaur
发表于 2020-10-10 10:03:51
题目 求的排列，有个限制条件，第个限制条件,表示前个数不能是的排列，求符合要求的排列的个数。 分析 这里是单纯计数的做法，时间复杂度设表示前个数均并且必须包含的方案数，初始化(如果第一个数有限制要特判)，最后输出首先可以写出一个朴素的方程，$i-1j1\sim jj-i+1jjjdp[i][i]= 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 xyq0220
发表于 2020-10-14 00:48:58
牛客练习赛71 C- 数学考试 题意 求 的排列，有 个限制条件，第个限制条件 表示前 个数不能是 的排列，求符合要求的排列的个数。 答案对 20000311 取模。 做法1 设为满足限制的情况下放好了排列的前个数且最大值为的方案数，转移如下： ，说明这一位有限制。 否则，，表示若，那 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 氧气少年Kevin
发表于 2022-06-03 10:45:46
牛客7745C - 数学考试 链接：https://ac.nowcoder.com/acm/contest/7745/C 知识点：组合数学,容斥,计数DP 难度：紫 题意 求 1∼n1∼n1∼n 的排列，有 mmm 个限制条件， 第 iii 个限制条件表示前 P[i]P[i]P[i] 个数不能是 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

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

扫描二维码，进入QQ群

扫码关注“比赛自动姬”