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了一下午 =。= 怪我不懂逆元，坑了兩位。

逆元：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