​​E - Permutation Counting​​(分类dp)

令

d

p

[

i

]

j

dp[i][j]

dp[i][j]表示前

i

i个数有

j

j个满足

a

k

>

k

a_k>k

ak​>k的答案。

分三种情况：

• 第

  i

  i

  i个数在位置

  i：没有影响：

  d

  p

  [

  ]

  j

  =

  −

  1

  dp[i][j]=dp[i-1][j]

  dp[i][j]=dp[i−1][j]

• i个数和某个满足

  a

  k

  >

  k

  a_k>k

  ak​>k的位置交换：

a

,

=

a_k>k,i=i

ak​>k,i=i交换之后

<

i>k,a_k<i

i>k,ak​<i，这样的数有

j个，所以是

−

×

dp[i-1][j]\times j

dp[i−1][j]×j

• 第

  i个数和某个满足

  a

  ≤

  a_k\le k

  ak​≤k的位置交换：

≤

a_k\le k,i=i

ak​≤k,i=i交换之后

i>k,ak​<i，增加了一个贡献，所以是

(

)

dp[i-1][j-1]\times (i-1-(j-1))

dp[i−1][j−1]×(i−1−(j−1))

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull; 
const int N=1e3+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
const int hashmod[4] = {402653189,805306457,1610612741,998244353};
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define x first
#define y second
#define pb emplace_back
#define SZ(a) (int)a.size()
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,a,b) for(int i=a;i>=b;--i)
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr) 
void Print(int *a,int n){
for(int i=1;i<n;i++)
printf("%d ",a[i]);
printf("%d\n",a[n]); 
}
int n,k;
ll dp[N][N];
int main(){
for(int i=1;i<N;i++){
dp[i][0]=1;
for(int j=1;j<i;j++)
dp[i][j]=(dp[i-1][j]*(j+1)+dp[i-1][j-1]*(i-j)%mod)%mod;
  }
while(~scanf("%d%d",&n,&k))
printf("%lld\n",dp[n][k]);
return 0;
}