CF鏈接：Almost Identity Permutations

Luogu鏈接：Almost Identity Permutations

$ {\scr \color {Aquamarine}{\text{Solution}}} $

前言

這好像是一道能用數學秒掉的題目

但由於我喜歡DP過菜，我們用DP來解決這個問題

分析

$ dp[i][j] $ 表示在 $ i $ 個數里有 $ j $ 個數位置滿足 $ a[i]==i $

答案很簡單，就是$\sum_{i=n-k}^{n} dp[n][i]$

接下來考慮狀態如何轉移

$ dp[i][j] $ 可以由 $ dp[i-1][j],dp[i-1][j-1],dp[i-1][j+1] $ 轉移而來

• 從 $ dp[i−1][j−1] $ 轉移，我們可以直接把新增的數放到增加的位置上去就可以了；
• 從 $ dp[i−1][j] $ 轉移，新增的數不能放到自己的位置上，且必須要和$ i-1-j $個其他的數字交換位置；
• 從 $ dp[i-1][j+1] $轉移，那麼新增的數字和原先在自己位置上的數字（j+1種）可以進行交換（因為現在多了一個，所以要減少一個）；

邊界也要稍稍註意一下

$ j=0 $時，並沒有$ dp[i-1][j-1]$

同理，$ i=j $時，直接為$ 1 $

誒，做完了

Code:

//From:201929
#include<bits/stdc++.h>
#define L long long
using namespace std;
L dp[1005][1005];
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    dp[4][4]=1,dp[4][3]=0,dp[4][2]=6,dp[4][1]=8,dp[4][0]=9;
    for(int i=5;i<=n;i++)
    for(int j=0;j<=i;j++)
    if(j==0) dp[i][j]=(i-1)*dp[i-1][j]+dp[i-1][1];
    else if(j==i) dp[i][j]=1;
    else dp[i][j]=dp[i-1][j-1]+(i-1-j)*dp[i-1][j]+(j+1)*dp[i-1][j+1];
    L ans=0;
    for(int i=n-k;i<=n;i++) ans+=dp[n][i];
    printf("%lld",ans);
    return 0;
}