• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

topcoder 8785 PSequence

开发技术 开发技术 3小时前 1次浏览
topc++oder 8785 PSequence

给出一个包含 (n) 个数的集合 (S) 和一个正整数 (p) ,求能组成多少种不同的序列,满足以下条件:

  1. (S) 中的元素都恰好包含一次.
  2. 序列中相邻两位(s_2-s_1) 不能被 (p) 整除.

(10^9+7).

(1leq nleq 30,1leq pleq 1000)

和 atcdoer tdpc o 题文字列超级像.

考虑按 (s_i) 的模数分类,相同一类不能相邻,那么一类一类地考虑 .

(cnt(i)) 统计 (%p)(i) 的个数有 (cnt(i)) ,令 (sum(i)=sumlimits^i cnt(j))

(dp(i,j)) 表示考虑到 (%p)(i) 的数,有 (j) 个相同相邻位子的方案数.

考虑模数为 (i+1) 的数.

首先,令 (cnt(i+1)) 个数分成了 (k) 段,其中 (x) 段放在了相同相邻位子的中间,那么,剩下 (k-x) 个就要放在 (m+1-j) 个位置上,此时,相同相邻位子的个数就是 (cnt(i+1)-k+j-x) .

(dp) 转移方程为

(cnt(i+1)!dbinom{cnt(i+1)-1}{k-1}dbinom{k}{x}dbinom{m+1-j}{k-x}dp(i,j) longrightarrow dp(i+1,cnt(i+1)-k+j-x))

本题还有一个非常坑的地方,一般情况下,%mod都是形如(x+y)%mod.

但是此题不可以!!!当 2*mod-2 相加的结果会爆 long long ,所以相加时要用 long long 保存.

时间复杂度 : (O(n^4))

空间复杂度 : (O(np))

code

#include<bits/stdc++.h>
using namespace std;
const long long mod=1234567891;
long long dp[1010][50];
long long C[50][50],P[50];
class PSequence{
public:
	int n;
	int cnt[1010];
	inline void upd(long long &x,long long y){x=(x+y)%mod;}
	int count(vector<int>a,int p){
		n=(int)a.size();
		for(int i=0;i<n;i++)a[i]=(a[i]%p+p)%p;
		for(int i=0;i<n;i++)cnt[a[i]]++;
		P[0]=1;
		for(int i=1;i<50;i++)P[i]=1ll*P[i-1]*i%mod;
		C[0][0]=1;
		for(int i=1;i<50;i++){
			C[i][0]=1;
			for(int j=1;j<=i;j++){
				upd(C[i][j],C[i-1][j-1]);
				upd(C[i][j],C[i-1][j]);
			}
		}
		dp[0][max(cnt[0]-1,0)]=P[cnt[0]];
		int m=cnt[0];
		for(int i=0;i+1<p;i++){
			if(cnt[i+1]==0){
				for(int j=0;j<=m;j++){
					upd(dp[i+1][j],dp[i][j]);
				}
			}
			else{
				for(int j=0;j<=m;j++){
					if(dp[i][j]==0)continue;
					for(int k=1;k<=cnt[i+1];k++)for(int x=0;x<=k;x++){
						if(m-j+1<k-x||j+cnt[i+1]-k-x<0)continue;
						long long tmp=1ll*P[cnt[i+1]]*C[cnt[i+1]-1][k-1]%mod;
						tmp=1ll*tmp*C[j][x]%mod;
						tmp=1ll*tmp*C[m-j+1][k-x]%mod;
						upd(dp[i+1][j+cnt[i+1]-k-x],1ll*dp[i][j]*tmp%mod);
					}	
				}
			}
			m+=cnt[i+1];
		}
		return dp[p-1][0];
	}
};

程序员灯塔
转载请注明原文链接:topcoder 8785 PSequence
喜欢 (0)