hdu 5378 概率dp 逆元

作者:盐城市天行软件有限公司  来源:www.szgjp.com未知  发布时间:2017-09-02 11:20:09
hdu 5378 概率dp 逆元 一棵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了一下午 =。= 怪我不懂逆元,坑了两位。

逆元: 大致就是除个数取模等于成该数的逆元再取模吧...

所以转移变成了:

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

企业建站2800元起,携手武汉肥猫科技,做一个有见地的颜值派!更多优惠请戳:武汉网页设计 http://www.feimao666.com


上一篇:武汉肥猫科技|有颜值又有见地的网站总是经久不衰
下一篇:最后一页