連結：https://tioj.ck.tp.edu.tw/problems/1201

題目大意

直線上有 $K$ 個房間，每個房間要不就是社團的人，要不就是怪人(沒社團的人)，任兩怪人之間要相隔 $M個房間，已知有 $N$ 種不同的社團，總共有幾種，問有幾種合法的人員放置方法，取除以 $P$ 的餘數。

題解

一開始想到數學解，由枚舉怪人的數量，再把方法數加起來，如果現在有 $S$ 位怪人，顯然要滿足：

$K \geq (S + (S - 1) \times M)$
$K \geq S + N$

可以先讓所有人以最緊密的方法排列進去，第一個是怪人，再下 $M$ 個空房間，然後再一個怪人，以此類推。最後會剩下 $K - (S + (S - 1) \times M)$ 間自由擺放的房間，數量用 $L$ 表示。根據排列組合， $L$ 個相同物有 $S + 1$ 個相異位置可放入，共有 $(\binom{L + S}{L})$ 種方法，故總方法數是 $\sum (\binom{L + S}{L}) \times N^{K - S}$ ，因為不能保證 $P$ 是質數，硬幹 $C_{m}^{n}$ 複雜度過高，化簡 $C$ 找通項DP化很麻煩，因此該方法不太合適。

如果是排組問題，可以考慮回到DP的基本想法，因為怪人的數量是任意多的，前面的怪人數量不影響答案，因此狀態可以如無限背包問題一樣，設 $d p [i] =$ 有 $i$ 個房間時，答案為何，考慮最後一個房間的狀況：

是怪人：那樣要扣掉 $1 + M$ 個位置給怪人與空位，答案有 $N^{M} \times d p [i - M - 1]$ 那麼多種
不是怪人：最後一個格子有 $N$ 種可能，答案有 $N \times d p [i - 1]$ 那麼多種

最後的答案即上兩狀況的和，狀態與轉移都超乾淨，複雜度是 $O (K)$

AC Code

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll dp[65536+1];
ll pw[65536+1];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    ll N,M,K,P,ans;
    
    while(cin>>N>>M>>K>>P,N)
    {
        ans = 0;
        pw[0]=dp[0]=1;
        for(ll i=1;i<=K;++i)
        {
            pw[i] = pw[i-1] * N % P;
            ll v1 = dp[i-1] * N % P;
            ll L = min(M,i-1) ;
            ll v2 = dp[i-1-L]*pw[L]%P;
            dp[i]=(v1+v2)%P;
        }
        cout<< dp[K] << '\n';
    }
}