Description
统计 \(1...n\) 的排列,恰好进行 \(k\) 次相邻交换和至多进行 \(k\) 次交换生成的不同的序列个数.
Sol
DP.
好妙的题啊...
首先看第一个问题.
对于相邻元素的交换,我们建立状态 \(f[i][j]\) 表示前 \(i\) 个数进行 \(j\) 次交换的方案数.
我们分类来讨论 \(i\) 元素是否参与交换.
如果不参与交换 \(f[i][j]+=f[i-1][j]\)
如果参与交换,那么它最远能交换到的位置就是 \(i-j\) \(f[i][j]+=f[i-1][u],max\{ i-j,0 \}\leqslant u \leqslant j-1\)
其实合起来就是 \(f[i][j]=\sum_{u=max\{0,i-j\}} ^{j} f[i-1][u]\) ,前缀和搞一下就可以了.
然后第二个问题.
继续来分类讨论 \(i\) 元素是否参与交换.
如果不参与交换 \(f[i][j]+=f[i-1][j]\)
如果参与交换,那么它可以和前面任意一个元素交换 \(f[i][j]+=f[i-1][j-1]*(i-1)\)
非常简单啊...
至于最后的判重就更简单了,因为换两次可以换回来,那么就让 \(f[i][j]-f[i][j-2]\) 这才是 \(f[i][j]\) 真正的贡献.
PS:我好像卡常卡到第一了...
Code
#include<cstdio>
#include<iostream>
using namespace std; typedef long long LL;
const int N = 3005;
const LL p = 1000000007;
#define debug(a) cout<<#a<<"="<<a<<" " int n,k;
LL f[N][N]; int main(){
cin>>n>>k;
f[1][0]=1;
for(int i=0;i<=k;i++) f[2][i]=i+1;
for(int i=3;i<=n;i++) for(int j=0;j<=k;j++){
int l=j-min(j,i-1)-1;
f[i][j]=(f[i-1][j]-(l>=0?f[i-1][l]:0LL)+p)%p;
f[i][j]=(f[i][j]+f[i][j-1])%p;
}
//for(int i=1;i<=n;i++) for(int j=0;j<=k;j++) printf("%lld%c",f[i][j]," \n"[j==k]);
cout<<(f[n][k]-f[n][k-1]+p)%p<<" "; f[1][0]=1;
for(int i=0;i<=k;i++) f[2][i]=1;
for(int i=3;i<=n;i++) for(int j=0;j<=k;j++){
f[i][j]=f[i-1][j];
f[i][j]=(f[i][j]+f[i-1][j-1]*(i-1)%p)%p;
}
//for(int i=1;i<=n;i++) for(int j=0;j<=k;j++) printf("%lld%c",f[i][j]," \n"[j==k]);
LL ans=0;
for(int i=k;i>1;i--) ans=(ans+f[n][i]-f[n][i-2]+p)%p;
ans=(ans+f[n][0]+f[n][1])%p;
cout<<ans<<endl; return 0;
}