hdu多校第九场题解(=100人)

虚拟比赛的时候就做了一道题。。晕。
A - Rikka with Nash Equilibrium
这题写了一个深搜，结果5*5都搜不出来呜呜呜
看别人的题解才知道是dp，dp[i][j][k]代表已经放了i个，占了j行k列的数量。
转移式子倒是挺好想的。。

#include<bits/stdc++.h>
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",n*m%K*dp[1][1][1]%K);}return 0;}

D - Rikka with Stone-Paper-Scissors
没仔细想就看题解了。。
我们来看R出石头的得分的期望，这个期望应该等于$\frac{(a-c)}{a+b+c}*b_1$,即为它出剪刀的概率减掉他出补的概率。(感觉怪怪的又感觉很有道理)
所以按照这种形式算一下就行了。

#include<bits/stdc++.h>
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<<gcd(-100,25)<<endl;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\n",up);else printf("%lld/%lld\n",up,down);}return 0;
}