1 条题解
-
1XzyStudio (admin) LV 8 MOD 机房蒟蒻 tayz @ 2023-10-13 10:16:41
破门而入(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; }
- 1
信息
- ID
- 1018
- 难度
- 9
- 分类
- (无)
- 标签
- 递交数
- 7
- 已通过
- 2
- 通过率
- 29%
- 上传者