[原创]CSU 1799 小Z的黑白棋 2016湖南省赛热身 [贡献式思维]【组合数学】

2016-09-05 17:17:27 Tabris_ 阅读数：346

博客爬取于2020-06-14 22:43:31
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/52441909

题目链接： http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1799
------------------------.

1799: 小Z的黑白棋
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 17 Solved: 9
[Submit][Status][Web Board]
Description
小Z有一些黑白棋，他觉得黑白混杂在一起极具美感，所以他总喜欢将这些棋子排成一排序列S1，但是小Y就喜欢跟小Z作对，她会趁小Z不注意偷偷将小Z最右边的棋子拿走，往他棋子序列的最左边添加一个白色的棋子形成一个新的序列S2来破坏小Z的美感。

S2(1~n) = 白棋+S1(i=1~n-1)

小Z总相信第一感，他认为他自己最初排好的序列S1是最完美的，新的序列S2会造成一定的破坏美感指数 = damage(S1) = S1与S2有多少个位置黑色与白色互不对应

Exp:

令白棋为a，黑棋为b :S1 = ababa S2=aabab damage(S1)=4

因为小Z有很多种摆放序列的方式，现在他希望让你帮他求所有摆放序列的方式会造成的damage(S1)的平均值

Input
多组数据输入输出

每组数据输入一个整数n和m表示白棋和黑棋的数量 0<=n , m<=1000,000,000 , 保证n+m>=1

Output
每组输出一个平均值答案，用最简分数表示，如果可以化简到整数，就用整数表示

Sample Input
1 1
Sample Output
3/2

---------------------------.

题目大意： 中文 不解释；

题解 ：
本题因为数据比较大 显然不能暴力
根据是n种白棋m种黑棋 先到组合数学的思路
n个白棋和m个黑棋有C(m+n,n)种排列。
然后就一直在想怎么才能直接组合出结果呢 半天后发现我根本就想不到啊
然后换了一种思路
求每个点对结果的贡献 最后累加就行了
就是这个位置对结果贡献1的排列有多少种就行了 这是能够排列组合出来的
分为下面两种情况
1，第一个点为黑棋的有C(m+n-1,n)种 因为后来变成了白棋 那么这就是第1个位置对结果的贡献
C(m+n-1,n)

2，第i（i=1,2,3…m+n-1）个棋子和第i+1个棋子颜色不同的 有2C(m+n-2,n-1)种 因为后来会发生错位的情况 那么这就是第i个位置对结果的贡献
2C(m+n-2,n-1)(m+n-1)=2n*C(m+n-1,n)

最后一推倒 就出来了这么一个公式
(1+2*n)C(m+n-1,n)/C(m+n,n)
=(1+2n)*m/(m+n)

贡献式思维主要就是求每个位置能对最后的结果贡献了多少 最后累加就行了

附本题代码
----------------------.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 505;
const double  Pi =  acos(-1);
# define pb push_back

LL gcd(LL a,LL b)
{
    if(!b) return a;
    else return gcd(b,a%b);
}

int main()
{
    int m,n;
    LL a,b;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        a=(n+n+1)*m;
        b=m+n;
        if(a%b==0)printf("%I64d\n",a/b);
        else  printf("%I64d/%I64d\n",a/gcd(a,b),b/gcd(a,b));
    }
    return 0;
}