hdu 5346 MZL's game dp

2015 Multi-University Training Contest 5  1004

当时全场没有队伍通过的一道题，此题状态构造的甚是巧妙

题意：n个人，每次从存活的人中等概率选出一个人去攻击场上其他人，被攻击者存活的概率相等 且由题目给出，选出的人出局。求一个人被攻击k次之后出局（被选出来攻击其他人后出局，受到攻击死亡不算出局）的概率。

思路：出题人的想法是先把这个问题转化为 从1，2...n顺次选取参与者去攻击其他人，如果被选者死亡，则直接选取下一个人即可。我们先处理出1，2...n的人受到 j 次攻击后存活的概率，dp[i][j]表示选取第 i 个人时，i 到 n的人都受到了 j 次攻击的概率，可以得到dp[i][j] = dp[i-1][j-1]*p1（第i-1个人受到j-1次攻击后存活的概率）+dp[i-1][j]*p2（第i-1个人在 j 次攻击内死亡的概率）。因为如果第 i-1 个人存活，那么必然会对i，i+1...n的人都进行一次攻击；只有当第i-1个人在之前的攻击中死亡，其余人才不会受到攻击。

一个人被攻击k次之后出局的概率其实就是dp[1,2...n][k]的和乘以p3（一个人受到k次攻击不死亡的概率）再除以n取平均数。在这里可以将dp[i][j]看作是第i个人受到j次攻击的概率。

最后：感谢队友提供的求逆元模板

#include "bits/stdc++.h"
using namespace std;
const long long PIVOT = 258280327;
long long P;

long long inv(long long x)
{
    if(x <= 1)
        return 1;
    return (PIVOT - PIVOT/x)*inv(PIVOT%x)%PIVOT;
}

long long n, x, y;
long long alive_K[2010];
long long dp[2010][2010];

int main()
{
    int T, i, j;
    scanf("%d", &T);
    while (T--) {
        scanf("%lld%lld%lld", &n, &x, &y);
        P = x * inv(y) % PIVOT;
        alive_K[0] = 1;
        for (i = 1; i <= n; ++i) {
            alive_K[i] = alive_K[i - 1] * (1 - P + PIVOT) % PIVOT;
        }

        dp[1][0] = 1;
        for (i = 2; i <= n; ++i) {
            for (j = 1; j < i; ++j) {
                dp[i][j] = dp[i - 1][j - 1] * alive_K[j - 1] % PIVOT + dp[i - 1][j] * (1 - alive_K[j] + PIVOT) % PIVOT;
                dp[i][j] %= PIVOT;
            }
        }

        long long res;
        int k;
        printf("%lld", inv(n));
        for (k = 1; k <= n - 1; ++k) {
            res = 0;
            for (i = 1; i <= n; ++i) {
                res += dp[i][k];
                res %= PIVOT;
            }
            res = res * alive_K[k] % PIVOT * inv(n) % PIVOT;
            printf(" %lld", res);
        }
        printf("\n");
    }
}