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

Tabris

CSDN数学组合数学

发布于：2016年9月5日

次浏览

[原创]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(1n) = 白棋 +S1(i=1n-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 个位置对结果的贡献
2 C(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;
}

本页文档最后更新于：2021年5月16日

CSDN

数学