在线安装软件网站开发,搜狗收录提交,网站做广告投放 要求做效果评估,安全优化大师题面
简要题意#xff1a;有一个 n n n 个点的图#xff0c;目前一条边都没有。有一个人在 1 1 1 号点要进行 m m m 次移动#xff0c; 终点不必是 1 1 1 号点。加入第 i i i 次的从 u u u 移动到了 v v v#xff0c; 那么 u u u 到 v v v 之间出现一条有向边。问…题面
简要题意有一个 n n n 个点的图目前一条边都没有。有一个人在 1 1 1 号点要进行 m m m 次移动 终点不必是 1 1 1 号点。加入第 i i i 次的从 u u u 移动到了 v v v 那么 u u u 到 v v v 之间出现一条有向边。问一共有多少序列满足最后 n n n 个点组成的图 是一个强联通图。答案对 1 0 9 7 10^9 7 1097 取模。 1 ≤ n m ≤ 300 1 \leq nm \leq 300 1≤nm≤300。
分析 注意到一个性质就是如果要形成强联通图那么所有的点都要和 1 1 1 能够相互到达。因为是从 1 1 1 出发所以序列里所有的点 1 1 1 都可以到达只要这 n n n 个点都能到达 1 1 1 那么这 n n n 个点组成的图就一定是一个强联通图。 我们根据这条性质来划分状态。 设 d p i , j , k dp_{i, j, k} dpi,j,k 表示当前已经走了 i i i 步涉及到的点有 j j j 个 跟 1 1 1 形成强联通的点有 k k k 个。注意当前点可以看做是没有跟 1 1 1 形成强联通的点。我们考虑转移 如果下一步走到了一个没有跟 1 1 1 形成强联通但是已经设计的点那么有 ( j − k ) × d p i , j , k → d p i 1 , j , k (j - k) \times dp_{i,j, k} \rightarrow dp_{i1, j, k} (j−k)×dpi,j,k→dpi1,j,k。 如果下一步走到了一个跟 1 1 1 形成强联通的点那么所有涉及到的点都会和 1 1 1 形成强联通有 k × d p i , j , k → d p i 1 , j , j k \times dp_{i, j, k} \rightarrow dp_{i1, j, j} k×dpi,j,k→dpi1,j,j。 如果下一步走到了一个还未涉及到的点那么有 ( n − j ) × d p i , j , k → d p i 1 , j 1 , k (n-j) \times dp_{i,j, k} \rightarrow dp_{i1,j1,k} (n−j)×dpi,j,k→dpi1,j1,k。 最后输出 d p m , n , n dp_{m,n,n} dpm,n,n 就好了。
#includebits/stdc.h
#define N 310
#define LL long long
#define mod 1000000007
using namespace std;
int n, m;
LL dp[N][N][N];// dp[i][j][k] 表示走了i步已经拓展了j个点 能与1形成强联通的点数为k 的方案数
int main(){cin n m;dp[0][1][1] 1LL;for(int i 0; i m; i){for(int j 1; j n; j){for(int k 1; k j; k){dp[i 1][j 1][k] (dp[i 1][j 1][k] dp[i][j][k] * (1LL * (n - j))) % mod;dp[i 1][j][k] (dp[i 1][j][k] dp[i][j][k] * (1LL * (j - k))) % mod;dp[i 1][j][j] (dp[i 1][j][j] dp[i][j][k] * (1LL * k)) % mod;}}}cout dp[m][n][n] endl;return 0;
}
