[原创]百度之星初赛2 瞬间转移 [杨辉三角]

2016-05-22 18:08:16 Tabris_ 阅读数：543

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

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

传送阵：http://acm.hdu.edu.cn/showproblem.php?pid=5698

瞬间移动

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 128 Accepted Submission(s): 61

Problem Description
有一个无限大的矩形，初始时你在左上角（即第一行第一列），每次你都可以选择一个右下方格子，并瞬移过去（如从下图中的红色格子能直接瞬移到蓝色格子），求到第n行第m列的格子有几种方案，答案对1000000007取模。

Input
多组测试数据。

两个整数n,m(2≤n,m≤100000)

Output
一个整数表示答案

Sample Input
4 5

Sample Output
10

Source
2016"百度之星" - 初赛（Astar Round2B）

其实写了写就是一个杨辉三角，只不过行变换了一下

杨辉三角是一个由数字排列成的三角形数表,一般形式如下：
　　1 n=0
　　1 1 n=1
　　1 2 1 n=2
　　1 3 3 1 n=3
　　1 4 6 4 1 n=4
　　1 5 10 10 5 1 n=5
　　1 6 15 20 15 6 1 n=6
　　……
特征
　　与二项式定理的关系：杨辉三角的第n行就是二项式展开式的系数列.
　　对称性：杨辉三角中的数字左、右对称,对称轴是杨辉三角形底边上的“高”.
　　结构特征：杨辉三角除斜边上1以外的各数,都等于它“肩上”的两数之和.
　　这些数排列的形状像等腰三角形,两腰上的数都是1.
　　从右往左斜着看,从左往右斜着看,和前面的看法一样,这个数列是左右对称的.
　　上面两个数之和就是下面的一行的数.
　　这行数是第几行,就是第二个数加一.

而在本题中是这样的、
　　1 1 1 1 1 1 1
　　1 2 3 4 5 6
　　1 3 6 10 15
　　1 4 10 20
　　1 5 15
　　1 6
　　1

看了看其实就是行变了列并没有变
把它改一下行变成行加列-1 即可；

最后的最后直接贴上求组合数的模板AC…

附本题AC 代码

方案1 187ms

# include <iostream>
# include <string.h>
# include <algorithm>
# include <math.h>
# include <vector>
# include <stdio.h>
using namespace std;

const int MOD = 1e9+7;

const int MAXN = 1000000;
bool arr[MAXN+100] = {false};

vector<int> produce_prim_number()
{
    vector<int> prim;
    prim.push_back(2);
    int i,j;
    for(i=3; i*i<=MAXN; i+=2)
    {
        if(!arr[i])
        {
            prim.push_back(i);
            for(j=i*i; j<=MAXN; j+=i)
            arr[j] = true;
        }
    }
    while(i<=MAXN)
    {
        if(!arr[i])
        prim.push_back(i);
        i+=2;
    }
    return prim;
}

//计算n!中素因子p的指数
int Cal(int x, int p)
{
    int ans = 0;
    long long rec = p;
    while(x>=rec)
    {
        ans += x/rec;
        rec *= p;
    }
    return ans;
}

//计算n的k次方对M取模，二分法
int Pow(long long n, int k, int MOD)
{
    long long ans = 1;
    while(k)
    {
        if(k&1)
        {
            ans = (ans * n) % MOD;
        }
        n = (n * n) % MOD;
        k >>= 1;
    }
    return ans;
}

//计算C(n,m)
int Combination(int n, int m)
{
    vector<int> prim = produce_prim_number();
    long long ans = 1;
    int num;
    for(int i=0; i<prim.size() && prim[i]<=n; ++i)
    {
        num = Cal(n, prim[i]) - Cal(m, prim[i]) - Cal(n-m, prim[i]);
        ans = (ans * Pow(prim[i], num, MOD)) % MOD;
    }
    return ans;
}

int main()
{
	int n,m;
	while(~scanf("%d%d",&n,&m))
	{
		n=m+n-2;

		printf("%d\n",Combination(n-2,m-2));
	}
	return 0;
}

方案 2 31ms

# include <iostream>
# include <cstdio>
# include <algorithm>
# include <cmath>
# include <cstring>
using namespace std;

# define lld  __int64

lld  n, m, p;

lld Ext_gcd(lld a,lld b,lld &x,lld &y)
{
   if(b==0) { x=1, y=0; return a; }
   lld ret= Ext_gcd(b,a%b,y,x);
   y-= a/b*x;
   return ret;
}

lld Inv(lld a,int m)   ///求逆元
{
   lld d,x,y,t= (lld)m;
   d= Ext_gcd(a,t,x,y);
   if(d==1) return (x%t+t)%t;
   return -1;
}

lld Cm(lld n, lld m, lld p)  ///组合数学
{
    lld a=1, b=1;
    if(m>n) return 0;
    while(m)
    {
        a=(a*n)%p;
        b=(b*m)%p;
        m--;
        n--;
    }
    return (lld)a*Inv(b,p)%p;  ///（a/b）%p 等价于 a*（b，p）的逆元
}

int Lucas(lld n, lld m, lld p)  ///把n分段递归求解相乘
{
    if(m==0) return 1;
    return (lld)Cm(n%p,m%p,p)*(lld)Lucas(n/p,m/p,p)%p;
}

int main()
{
    int  T;
    while(~scanf("%I64d%I64d",&n,&m))
    {
    	n--,m--;
		m--;
        __int64 p=1000000007;

        printf("%d\n",Lucas(n+m-1,m,p));
    }
    return 0;
}