山东省第八届省赛 sdut 3896(找规律+组合数取模)
程序员文章站
2022-06-05 22:09:47
...
题意:
如图让你求从(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);
}
}
上一篇: Python正则获取、过滤或者替换HTML标签的方法
下一篇: 小鑫の日常系列故事(七)——小纸条