一棵n个节点的树。对其节点进行标号(1~n)。求恰好存在k个节点的标号是其节点所在子树的最大值的方案数。
首先，总共有n！中标号方案。而如果求出n个节点中出现k个上述节点的概率p。方案数等于n！* p。
dp[i][j] 表示钱i个节点有j个上述节点的概率。转移较容易推出。
dp[i][j] = dp[i-1][j] * (c[i]-1) / c[i] + dp[i-1][j-1] * (1 / c[i]); c[i] 第i个节点的子树的节点数。
?
然后，double肯定是不能过的。于是傻傻用结构体存了个分数。然后分母乘起来爆long long了。然后和GT，喵呜三个debug了一下午 =。= 怪我不懂逆元，坑了两位。
逆元：www.2cto.com 大致就是除个数取模等于成该数的逆元再取模吧...
所以转移变成了:
?
dp[i][j] = dp[i-1][j] * (c[i]-1) * Inv(c[i]) + dp[i-1][j-1] * Inv(c[i])
然后dp就是在整数里面转移了。
?
?
/***********************************************
** problem ID : hdu_5378.cpp
** create time : Wed Aug 12 11:14:30 2015
** auther name : xuelanghu
** auther blog : blog.csdn.net/xuelanghu407
**********************************************/
#include
#include
#include
#include
#include
using namespace std; const int MAXN = 1000 + 5; const long long MOD = (long long)(1e9 + 7); struct Node { long long a, b; Node() {a = 0; b = 1;} Node(long long _a, long long _b): a(_a), b(_b) {} }; long long _gcd(long long a, long long b) { if (b == 0) return a; else return _gcd(b, a%b); } inline Node add (Node x, Node y) { long long rec, res, tmp; rec = x.a*y.b + x.b*y.a; res = x.b*y.b; tmp = _gcd(rec, res);// if (tmp == 0) tmp = 1; return Node(rec/tmp, res/tmp); } inline Node mul (Node x, Node y) { long long rec, res, tmp; rec = x.a * y.a; res = x.b * y.b; tmp = _gcd(rec, res);// if (tmp == 0) tmp = 1; return Node(rec/tmp, res/tmp); } int n, k; vector
v[MAXN]; long long dp[MAXN][MAXN]; long long c[MAXN]; long long dfs(int t, int fa) { long long cnt = 1L; for (int i=0; i
>= 1; } return res; } long long Inv(long long a) { return power(a, MOD-2); } long long _In[MAXN]; void init() { for (int i=1; i<=1002; i++) { _In[i] = Inv(i); } } long long f(int n) { long long res = 1; for (int i=1; i<=n; i++) { res = (res * (long long) (i)) % MOD; } return res; } int main () { int T_case; init(); scanf(%d, &T_case); for (int i_case=1; i_case<=T_case; ++i_case) { scanf (%d%d, &n, &k); for (int i=0; i<=n; i++) v[i].clear(); // memset(c, 0,sizeof(c)); int a, b; for (int i=1; i
?
?