hdu 다교 제9장 문제풀이(>=100명)

사이버 게임 때 한 문제만 풀었어.어지럽다A-Rikka with Nash Equilibrium 이 문제를 심층 검색한 결과 5*5를 찾을 수 없었습니다ㅠㅠ 다른 사람의 문제풀이를 보고 dp임을 알았습니다. dp[i][j][k]는 i개를 넣었고 j행k열의 수량을 차지했습니다.전이식은 너무 보고 싶은데.

#include
using namespace std;
long long dp[85*85][85][85];
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,m,K;
        scanf("%d %d %d",&n,&m,&K);
        dp[n*m][n][m]=1;
        for(int i=n*m-1;i>=1;i--)
        {
            for(int j=n;j>=1;j--)
                for(int k=m;k>=1;k--)
            {
                if(i>j*k)break;
                dp[i][j][k]=(n-j)*k%K*dp[i+1][j+1][k]%K;
                dp[i][j][k]=(dp[i][j][k]+(m-k)*j%K*dp[i+1][j][k+1]%K)%K;
                dp[i][j][k]=(dp[i][j][k]+((j*k%K-i)%K+K)%K*dp[i+1][j][k]%K)%K;
            }
        }
        printf("%lld
",n*m%K*dp[1][1][1]%K);
    }
    return 0;



}

D-Rikka with Stone-Paper-Scissors는 자세히 생각하지 않고 문제를 풀었다.우리가 R이 돌을 내는 득점에 대한 기대를 보면 이 기대는 (a-3-c)a+b+c∗b1(a-3c)a+b+c\8727b1;b1과 같다. 즉, 가위를 낼 확률로 그가 보태는 확률을 줄여야 한다.(이상하고 일리가 있는 것 같아) 그러니까 이런 식으로 계산하면 돼.

#include
using namespace std;
long long gcd(long long a,long long b)
{
    if(a<0)a=-a;
    return b==0?a:gcd(b,a%b);
}
int main()
{

    //cout<

    int T;
    scanf("%d",&T);
    while(T--)
    {
        long long a,b,c,a1,b1,c1;
        scanf("%lld %lld %lld %lld %lld %lld",&a,&b,&c,&a1,&b1,&c1);
        long long up=(a-c)*b1+(c-b)*a1+(b-a)*c1;
        long long down=a+b+c;
        long long tmp=gcd(up,down);
        up=up/tmp,down=down/tmp;
        if(down==1)printf("%lld
",up);
        else printf("%lld/%lld
",up,down);
    }
    return 0;
}