在线时间:8:00-16:00
迪恩网络APP
随时随地掌握行业动态
扫描二维码
关注迪恩网络微信公众号
[题目链接] https://www.lydsy.com/JudgeOnline/problem.php?id=2302 [算法] 记 s[i] 表示已经确定的m人中编号大于等于i的人数 考虑dp , 记fi,j表示剩余(n - m)人中编号大于等于i的人已经确定j个人的编号的方案数,则:f[i][j] = sigma(f[i + 1][j - k] * C(j , k)) 时间复杂度 : O(N ^ 3) [代码]
#include<bits/stdc++.h> using namespace std; #define N 310 typedef long long ll; typedef long double ld; typedef unsigned long long ull; int n , m , M; int cnt[N] , C[N][N] , dp[N][N]; template <typename T> inline void chkmax(T &x,T y) { x = max(x,y); } template <typename T> inline void chkmin(T &x,T y) { x = min(x,y); } template <typename T> inline void read(T &x) { T f = 1; x = 0; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = -f; for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - '0'; x *= f; } int main() { int T; read(T); while (T--) { read(n); read(m); read(M); memset(cnt , 0 , sizeof(cnt)); memset(C , 0 , sizeof(C)); memset(dp , 0 , sizeof(dp)); for (int i = 1; i <= m; ++i) { int x , y; read(x); read(y); ++cnt[y]; } for (int i = n; i >= 1; --i) cnt[i] += cnt[i + 1]; bool tag = true; for (int i = 1; i <= n; ++i) { if (cnt[i] > n - i + 1) tag = false; } if (!tag) { printf("NO\n"); continue; } for (int i = 0; i <= n; ++i) { C[i][0] = 1; for (int j = 1; j <= i; ++j) C[i][j] = (1LL * C[i - 1][j] + 1LL * C[i - 1][j - 1]) % M; } dp[n + 1][0] = 1; for (int i = n; i >= 1; --i) { for (int j = 0; j <= n - i + 1 - cnt[i]; ++j) { for (int k = 0; k <= j; ++k) { dp[i][j] = (dp[i][j] + 1LL * dp[i + 1][j - k] % M * C[j][k] % M) % M; } } } printf("YES %d\n" , dp[1][n - m]); } return 0; }
|
2023-10-27
2022-08-15
2022-08-17
2022-09-23
2022-08-13
请发表评论