Hdu 6821 Set2 —— dp，優化

This way

題意：

現在有一個1~n的排列，每次會先拿走最小的數，然後再拿走随機k個數，知道留下小于等于k個數為止，問你每個數被留下的機率。

題解：

首先這道題的範圍隻有5000，那麼可以考慮 O ( n 2 ) O(n^2) O(n2)的時間複雜度。

dp[i][j]表示剩下i個數的時候，目前的數是第j個的時候的機率。

那麼它是從dp[i-k-1]推過來的，假設它删掉了j前面的L個數，j後面的k-L個數，到達了dp[i-k-1][j-L-1]，但是很明顯這樣我們正着推是無法得出來每個數的機率的，是以要反着推，從dp[i-k-1]先放k個數，再放一個最小的數推到dp[i]。

那麼我們假設放的k個數中，有L個比j小的，有k-L個比j大的，于是狀态轉移方程就寫出來了：

d p [ i ] [ j ] = ∑ L = m a x ( 0 , k − i + j ) m i n ( j − 2 , k ) C j − 2 L C i − j k − L d p [ i − k − 1 ] [ j − L − 1 ] C i − 1 k dp[i][j]=\frac{\sum\limits_{L=max(0,k-i+j)}^{min(j-2,k)}C_{j-2}^{L}C_{i-j}^{k-L}dp[i-k-1][j-L-1]}{C_{i-1}^{k}} dp[i][j]=Ci−1k​L=max(0,k−i+j)∑min(j−2,k)​Cj−2L​Ci−jk−L​dp[i−k−1][j−L−1]​

一些地方-1是因為有一個拿掉最小的數的限制。

顯然，這是 O ( n 3 ) O(n^3) O(n3)的做法，但是我們發現i其實是定的，每次跳k+1，總共跳n/k次，然後L的範圍最大也是k，是以兩個循環的時間複雜度乘起來也就是n，其實最終時間複雜度是O(n^2）的。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=5e3+5;
const ll mod=998244353;
ll dp[N][N],fac[N],inv[N];
ll qpow(ll a,ll b){ll ans=1;for(;b;b>>=1,a=a*a%mod)if(b&1)ans=ans*a%mod;return ans;}
ll c[N][N],invc[N][N];
int main()
{
    fac[0]=inv[0]=1;
    for(ll i=1;i<N;i++)fac[i]=fac[i-1]*i%mod;
    inv[N-1]=qpow(fac[N-1],mod-2);
    for(ll i=N-2;i;i--)inv[i]=inv[i+1]*(i+1)%mod;
    for(int i=0;i<N;i++)
        for(int j=0;j<=i;j++)
            c[i][j]=fac[i]*inv[j]%mod*inv[i-j]%mod,invc[i][j]=fac[i-j]*fac[j]%mod*inv[i]%mod;
    int t;
    scanf("%d",&t);
    while(t--){
        int n,k;
        scanf("%d%d",&n,&k);
        int res=n%(k+1);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                dp[i][j]=0;
        for(int i=1;i<=res;i++)dp[res][i]=1;
        for(int i=res+k+1;i<=n;i+=k+1)
            for(int j=1;j<=i;j++)
                for(int l=max(0,k-i+j);l<=k&&l<=j-2;l++)
                    dp[i][j]=(dp[i][j]+c[j-2][l]*c[i-j][k-l]%mod*dp[i-k-1][j-l-1]%mod*invc[i-1][k])%mod;
        for(int i=1;i<=n;i++)
            printf("%lld%c",dp[n][i]," \n"[i==n]);
    }
    return 0;
}