P3867 [TJOI2009] 排列计数
题解
\(k\) 很小，不是分讨就是突破口。如果我们用这种方式生成排列：将 \(1\) 到 \(n\) 按顺序插入当前状态，那么你会发现当前的数 \(x\) 的插入被很大程度的限制住了，我们只需记录当前 \(x-k\) 到 \(x-1\) 的位置即可枚举出所有可能的下一状态，因此我们可以使用更新式 \(dp\)。
状态 \(f_{i,S}\) 表示长度为 \(i\) 的排列，当前 \(x-k\) 到 \(x-1\) 的位置为 \(S\) 的方案数，其中的 \(S\) 本质上是一个 \(k\) 维数组。
对于状态 \(f_{i,S_1,S_2,\cdots,S_k}\)：如果 \(S\) 中有一个数在位置 \(1\)，那就说明 \(i+1\) 可以被插入在 \(1\)，因此更新 \(f_{i+1,1,S_1+1,S_2+1,\cdots,S_{k-1}+1}\)。末尾同理。如果存在 \(S_l=S_r-1\)，那么 \(i+1\) 可以被插入在 \(S_r\)，因此更新 \(f_{i+1,S_r,S_1',S_2',\cdots,S_{k-1}'}\)，其中的 \(S'\) 需要考虑插入后会不会后移一位。
空间 \(128MB\) 可能会爆，把第一维滚动掉就好了。这样空间复杂度 \(O(n^k)\)，时间复杂度 \(O(n^{k+1})\)。
好像就是这样了，虽然代码比较长，不过其实不难写。马蜂很乱，我也不准备解释了，如果你真的想看的话：
/*
* @Author: operator_
* @Date: 2024-01-16 13:50:22
* @Last Modified by: operator_
* @Last Modified time: 2024-01-16 14:44:53
*/
#include<bits/stdc++.h>
using namespace std;
inline int rd() {
int s=0,m=0;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-')m=1;ch=getchar();}
while( isdigit(ch)) s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
return m?-s:s;
}
const int M=1e9+7;
#define U2 f[!i][p][a1+(a1>=p)]=(f[!i][p][a1+(a1>=p)]+f[i][a1][a2])%M
#define U3 f[!i][p][a1+(a1>=p)][a2+(a2>=p)]=(f[!i][p][a1+(a1>=p)][a2+(a2>=p)]+f[i][a1][a2][a3])%M
#define U4 f[!i][p][a1+(a1>=p)][a2+(a2>=p)][a3+(a3>=p)]=(f[!i][p][a1+(a1>=p)][a2+(a2>=p)][a3+(a3>=p)]+f[i][a1][a2][a3][a4])%M
int n,k,p,tmp[55],Ans;
signed main(){
cin>>n>>k;
if(k==1) return cout<<min(n,2),0;
if(k==2) {
int f[2][51][51];memset(f,0,sizeof(f));
f[1][1][0]=1;
for(int ii=1;ii<n;ii++) {
int i=ii&1;memset(f[!i],0,sizeof(f[!i]));
for(int a1=0;a1<=ii;a1++) {
for(int a2=0;a2<=ii;a2++) {
tmp[a1]++,tmp[a2]++,tmp[0]=0;
if(tmp[a1]<2&&tmp[a2]<2) {
if(tmp[1]) p=1,U2;
if(tmp[ii]) p=ii+1,U2;
if(tmp[a1]&&tmp[a1+1]) p=a1+1,U2;
if(tmp[a2]&&tmp[a2+1]) p=a2+1,U2;
}
tmp[a1]--,tmp[a2]--;
}
}
}
for(int a1=0;a1<=n;a1++)
for(int a2=0;a2<=n;a2++)
Ans=(Ans+f[n&1][a1][a2])%M;
return cout<<Ans,0;
}
if(k==3) {
int f[2][51][51][51];memset(f,0,sizeof(f));
f[1][1][0][0]=1;
for(int ii=1;ii<n;ii++) {
int i=ii&1;memset(f[!i],0,sizeof(f[!i]));
for(int a1=0;a1<=ii;a1++) {
for(int a2=0;a2<=ii;a2++) {
for(int a3=0;a3<=ii;a3++) {
tmp[a1]++,tmp[a2]++,tmp[a3]++,tmp[0]=0;
if(tmp[a1]<2&&tmp[a2]<2&&tmp[a3]<2) {
if(tmp[1]) p=1,U3;
if(tmp[ii]) p=ii+1,U3;
if(tmp[a1]&&tmp[a1+1]) p=a1+1,U3;
if(tmp[a2]&&tmp[a2+1]) p=a2+1,U3;
if(tmp[a3]&&tmp[a3+1]) p=a3+1,U3;
}
tmp[a1]--,tmp[a2]--,tmp[a3]--;
}
}
}
}
for(int a1=0;a1<=n;a1++)
for(int a2=0;a2<=n;a2++)
for(int a3=0;a3<=n;a3++)
Ans=(Ans+f[n&1][a1][a2][a3])%M;
return cout<<Ans,0;
}
if(k==4) {
int f[2][51][51][51][51];memset(f,0,sizeof(f));
f[1][1][0][0][0]=1;
for(int ii=1;ii<n;ii++) {
int i=ii&1;memset(f[!i],0,sizeof(f[!i]));
for(int a1=0;a1<=ii;a1++) {
for(int a2=0;a2<=ii;a2++) {
for(int a3=0;a3<=ii;a3++) {
for(int a4=0;a4<=ii;a4++) {
tmp[a1]++,tmp[a2]++,tmp[a3]++,tmp[a4]++,tmp[0]=0;
if(tmp[a1]<2&&tmp[a2]<2&&tmp[a3]<2&&tmp[a4]<2) {
if(tmp[1]) p=1,U4;
if(tmp[ii]) p=ii+1,U4;
if(tmp[a1]&&tmp[a1+1]) p=a1+1,U4;
if(tmp[a2]&&tmp[a2+1]) p=a2+1,U4;
if(tmp[a3]&&tmp[a3+1]) p=a3+1,U4;
if(tmp[a4]&&tmp[a4+1]) p=a4+1,U4;
}
tmp[a1]--,tmp[a2]--,tmp[a3]--,tmp[a4]--;
}
}
}
}
}
for(int a1=0;a1<=n;a1++)
for(int a2=0;a2<=n;a2++)
for(int a3=0;a3<=n;a3++)
for(int a4=0;a4<=n;a4++)
Ans=(Ans+f[n&1][a1][a2][a3][a4])%M;
return cout<<Ans,0;
}
return 0;
}
其实想简化的话办法也很多，一个最可行的是直接存 \(S\) 的哈希值，不过我懒了。
标签：ch,题解,a1,插入,a3,a2,P3867 From： https://www.cnblogs.com/operator-/p/17974764