【luogu SP7685】FLWRS - Flowers(DP)(容斥)
2022/8/27 23:53:06
本文主要是介绍【luogu SP7685】FLWRS - Flowers(DP)(容斥),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
FLWRS - Flowers
题目链接:luogu SP7685
题目大意
给你模数 m,问你有多少个长度为 n 的排列满足相邻两个差不为 1。
思路
首先一个简单的想法是容斥。
那有 \(n\) 对相邻的不满足,就乘上 \((-1)^n\)。
考虑如何统计,首先考虑不看数,就看每个位置是否会不满足。
于是能设计出一个 DP 为 \(f_{i,j,0/1}\) 是前 \(i\) 个数,已经有 \(j\) 对地方不满足,当前位置跟前面满足 / 不满足。
然后第一次不满足你要安排顺序,顺着还是逆着,那一开始固定了不满足的一段后面都固定了。
然后你考虑对于 \(f_{n,i,0/1}\),它怎么给答案进行贡献。
首先容斥系数 \(-1\)(当然你可以放在 DP 里面)。
另外就是你要安排一下给的数,考虑怎么安排:
发现我们可以把每段连续的不合法捆成一个,那因为你 DP 里面固定了顺序,所以你可以直接可以用左端点或者右端点代表它。
那我们只需要找到它们之间的相对大小,所以我们只需要乘上 \((n-i)!\) 即可。
代码
#include<cstdio> #define ll long long using namespace std; const int N = 2005; int n; ll mo, f[N][N][2], jc[N]; int main() { scanf("%d %lld", &n, &mo); jc[0] = 1; for (int i = 1; i < N; i++) jc[i] = jc[i - 1] * i % mo; f[1][0][0] = 1; for (int i = 2; i <= n; i++) { f[i][0][0] = f[i - 1][0][0]; for (int j = 1; j <= i; j++) { f[i][j][0] = (f[i - 1][j][0] + f[i - 1][j][1]) % mo; f[i][j][1] = (mo - (f[i - 1][j - 1][0] * 2 + f[i - 1][j - 1][1]) % mo) % mo; } } ll ans = 0; for (int i = 0; i < n; i++) (ans += jc[n - i] * (f[n][i][0] + f[n][i][1]) % mo) %= mo; printf("%lld", ans); return 0; }
这篇关于【luogu SP7685】FLWRS - Flowers(DP)(容斥)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28微服务架构中API版本控制的实践
- 2024-09-28AI给的和自己写的Python代码,都无法改变输入框的内容,替换也不行
- 2024-09-27Sentinel配置限流资料:新手入门教程
- 2024-09-27Sentinel配置限流资料详解
- 2024-09-27Sentinel限流资料:新手入门教程
- 2024-09-26Sentinel限流资料入门详解
- 2024-09-26Springboot框架资料:初学者入门教程
- 2024-09-26Springboot框架资料详解:新手入门教程
- 2024-09-26Springboot企业级开发资料:新手入门指南
- 2024-09-26SpringBoot企业级开发资料新手指南