破门而入(broken)

将每个房间看成一个节点，里面放的钥匙看成指向另一个房间对应节点的有向边，则能够打开所有房门当且仅当房间形成了不超过\(k\)个有向环 (注意每个房间的出度恰好为\(1\)，所以不会形成更复杂的有向图)
那么问题就变成了将\(n\)个不同的物品嵌入到不超过\(k\)个环上的方案数，如果将“不超过”改为恰好，这就是第一类Stirling数的定义，所以答案就是第一类Stirling数的前缀和，直接递推即可，时问复杂度\(O(n^2)\)

#include<bits/stdc++.h>
#define MAXN 3005
#define MOD 998244353
#define INF 1e9
using namespace std;

long long ans, n, k;
long long s[MAXN][MAXN];

int main(){
    // freopen("broken.in", "r", stdin);
    // freopen("broken.out", "w", stdout);
    //  freopen(".err", "w", stderr);
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);cerr.tie(0);
    
    cin>>n>>k;
    s[0][0] = 1;
    
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= k; j++){
            s[i][j] = (s[i - 1][j - 1] + s[i - 1][j] * (i-1)) % MOD;
        }
    }

    for(int i=1; i<=k; i++){
        ans += s[n][i] % MOD;
    }

    ans %= MOD;
    cout<<ans<<endl;
    
    return 0;
}