咕咕咕了太久 多校博客直接从第三场跳到了第九场orz 见谅见谅（会补的！）
明明最后看下来是dp场 但是硬生生被我们做成了组合数专场…… 听说jls把我们用组合数做的题都用dp来了遍 这里只放了用组合数的题目 dp的还没有补（这又是一个大坑orz）
1001 Rikka with Nash Equilibrium (hdoj 6415)
链接：http://acm.hdu.edu.cn/showproblem.php?pid=6415
题意：给一个n*m的矩阵 其中放着从1到n*m的严格不想等的数字 只能有一个位置的数字在这一行这一列都是最大 求这样的排放方案数 并且将方案数对k取模 其中k并不是质数
想到了用概率的思想去做 一个数放在每个位置上的概率都是相等的 先放最大的那个数 若放在列上 则有n!种放置方法 若放在行上 则有m!种放置方法 而一行一列则是有(n+m-1)个位置 所以放置位置的概率就是
n!*m!/(n+m-1)!，最后是n*m个数的全排列
推出来的式子为:n!*m!/(n+m-1)!*(n*m)!
代码如下：
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; typedef long long ll; ll t,n,m,k,ans; ll comb(ll x){ ll sum=1; for(int i=1;i<=x;i++){ sum=(sum*i)%k; } return sum; } int main(){ scanf("%lld",&t); while(t--){ scanf("%lld%lld%lld",&n,&m,&k); ll ans=comb(n)*comb(m)%k; ll t1=n+m,t2=n*m; ll res=1; for(int i=t1;i<=t2;i++){ res=(res*i)%k; } ans=(ans*res)%k; printf("%lld ",ans); } return 0; }
1004 Rikka with Stone-Paper-Scissors (hdoj 6418)
链接：http://acm.hdu.edu.cn/showproblem.php?pid=6418
签到题
题意：两方博弈 自己一方剪刀 石头 布的数量分别为x y z 对方为a b c 算出自己获胜的概率 需要约分
需要注意到的就是负数情况
代码如下 一些必要的注释已经写在里面了
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; int t; ll a,b,c,x,y,z,n,t1,t2,t3,p,d; ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} int main(){ scanf("%d",&t); while(t--){ cin>>a>>b>>c>>x>>y>>z; n=a+b+c; t1=x*(c-b); //x做出的贡献 t2=y*(a-c); //y做出的贡献 t3=z*(b-a); //z做出的贡献 p=t1+t2+t3; d=gcd(p,n); //约分 if(d<0) d=-d; p/=d; n/=d; if(n==1) cout<<p<<endl; else cout<<p<<"/"<<n<<endl; } return 0; }