topcoder 8785 PSequence
给出一个包含 \(n\) 个数的集合 \(S\) 和一个正整数 \(p\) ，求能组成多少种不同的序列，满足以下条件：
- \(S\) 中的元素都恰好包含一次.
- 序列中相邻两位\(s_2-s_1\) 不能被 \(p\) 整除.
模 \(10^9+7\).
\(1\leq n\leq 30,1\leq p\leq 1000\)
和 atcdoer tdpc o 题文字列超级像.
考虑按 \(s_i\) 的模数分类，相同一类不能相邻，那么一类一类地考虑 .
令 \(cnt(i)\) 统计 \(\%p\) 余 \(i\) 的个数有 \(cnt(i)\) ，令 \(sum(i)=\sum\limits^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];
}
};