CodeForces - 1284C New Year and Permutation(组合数学+思维)

题目链接：点击查看

题目大意：首先定义名词“排列”的意思是，一段数列中的数字升序排序后可以组成连续的一段数列，换句话说，满足一段区间内的最大值-最小值=r-l则称这个区间的数列为“排列”，规定每个满足“排列”的子数列对答案的贡献为1，比如对于数列(6,7,1,8,5,3,2,4)，其满足“排列”的子数列分别为[1,2],[5,8],[6,7],[3,3],[8,8]，贡献为5。现在给出一个数字n和模mod，问长度为n的全排列的贡献是多少，答案对mod取模

题目分析：看了题解之后才知道是一个非常简单的排列组合的题目，但当时自己却在往dp上想，虽然都是需要推公式，但感觉自己在数学方面真的弱死了

回到这个题目上来，因为是全排列，所以肯定和阶乘脱不了干系，可以先预处理出一个对模取余后的阶乘，接下来枚举每个子数列是不太现实的，因为有n*n个，加上全排列后是n*n*(n!)个，那么我们能不能换一种思想，去枚举子数列的长度len，从而计算长度为len的子数列对答案的贡献呢？

首先对于一个长度为len的数列，只要这len个数前后连在一起，那么其贡献都是1，也就是有len!种内部排列方案，同时除了这len个数之外，还有n-len个数，如果将刚才绑定在一起的len个数视为整体，当前还有n-len+1个数是无序的，其全排列的方案数也是有(n-len+1)!种方法，所以对于一个长度为len的数列，其对答案的贡献就是(len!)*((n-len+1)!)，那么共有多少个长度为len的数列呢，相当于尺取的思想，令起点从最左边向右边移动，每次都取len个元素构成子数列，这样共有(n-len+1)种不同的子序列，故长度为len的子序列对答案的贡献就是上面分析的乘起来就好了：(len!)*((n-len+1)!)*(n-len+1)

记得日常%一%防爆

代码：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e6+100;LL fac[N],mod;void init() {fac[0]=1;for(int i=1;i<N;i++)fac[i]=fac[i-1]*i%mod; }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int n;scanf("%d%lld",&n,&mod);init();LL ans=0;for(int len=1;len<=n;len++)ans=(ans+fac[len]*fac[n-len+1]%mod*(n-len+1)%mod)%mod;printf("%lld\n",ans);return 0; }

 

总结

以上是生活随笔为你收集整理的CodeForces - 1284C New Year and Permutation(组合数学+思维)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。