欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

山东省第八届省赛 sdut 3896(找规律+组合数取模)

程序员文章站 2022-06-05 22:09:47
...

题意:

山东省第八届省赛 sdut 3896(找规律+组合数取模)

如图让你求从(1,1)到(A,B)有多少种方案。


解题思路:


设向左走l步,向下走r步,向下走c步,我们枚举c,当c确定的时候,l和r也同时确定了,然后求一下l,r,c的排列数(l+r+c)!/(l!*r!*c!)就好了。


需要预处理阶乘的逆元。


具体见代码:

#include <bits/stdc++.h>
#define LL long long 
using namespace std;
const int mod=1e9+7;
const int maxn=2e5+5;
LL num[10*maxn];
LL A[maxn];

long long pw(int a,int b)
{
    long long sum=1,base=a;
    while(b)
    {
        if(b%2)sum=(sum*base)%mod;
        base=(base*base)%mod;
        b=b/2;
    }
    return sum;
}

void init() //预处理
{
    num[0]=0;
    num[1]=1;
    A[1]=1;
    for(int i=2; i<=maxn-2; i++)
    {
        num[i]=(num[i-1]*i)%mod; //预处理阶乘
        A[i]=pw(num[i], mod-2)%mod; //预处理逆元
    }
    return;
}


LL F(int a, int b, int c)
{
    if(a==b && b==c && c==0)return 1LL;
    LL res=num[a+b+c];
    
    if(num[a]>0)res=(res*A[a])%mod;   
    if(num[b]>0)res=(res*A[b])%mod;
    if(num[c]>0)res=(res*A[c])%mod;   
    return res;
}
int main()
{
    init();
   int a, b, x, i, y, j, l, r;
   while(~scanf("%d%d", &a, &b))
   {
        LL ans=0;
    
        if(b<=a/2)
        {
            x=a-2*b+1; //距离中心的横坐标偏移量 一步相当于2个纵坐标偏移
            y=a-1;//距离(1,1)的纵坐标偏移
            for(i=0; i<=(y-x)/2; i++)
            {
               l=(x+y-2*i)/2;//往左走的步数
               r=y-2*i-l;//往右走的步数
               ans=(ans+F(l, r, i))%mod;
            }
        }
        else 
        {
            x=2*b-1-a;//距离中心的横坐标偏移量
            y=a-1;
            for(i=0; i<=(y-x)/2; i++)//枚举往下走的步数  一步相当于2个纵坐标偏移
            {
               l=(y-2*i-x)/2; //往左走的步数  
               r=y-2*i-l;//往右走的步数
               ans=(ans+F(l, r, i))%mod;
            }
        }
        printf("%lld\n", ans%mod);
        
   } 
}






相关标签: acm sdut