Hopscotch(组合数计算)
题目链接：http://exam.upc.edu.cn/problem.php?id=5095
题目大意：给你一个N , X , Y--n的距离从(0 , 0)->（n , n）
且每一步都不能走的路程沿X轴方向不能小于X, 沿Y轴方向不小于Y。
问题是：问有多少种方法能走到终点。（n,n）
题解：
首先我们可以确定的是 一步走过去吧。
而第二步是 确定前后的距离 之间的都可以
举例子（n=7, x=2）
0 1 2 3 4 5 6 7
× × @ @ @ @ × ×
('X' 是两步时不能走的区域， '@' 是可以走的区域)。
所以对于 N=7,且 X = 2 走两步的情况有4种
同理可得 Y = 3 走两步的情况有2种
所以示例中所给的N=7，X=2，Y=3
ans= 1 + 2×4 = 9;
(一步) (两步)
可以看出来，答案应该是对应的步数是的方案数相乘最后就累加起来，
for（ 1 ～ min（N/X，N/Y））
ans +=（X[ i ] * Y[ i ]）
至于在第几步中对于它的方案数怎么求呢?
若该数是21 ，x为3或4
表如下：
步数 1 2 3 4 5
3 1 16 91 220 210
4 1 14 55 56 5
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1
1 11 55 165 330 462 462 330 165 55 11 1
1 12 66 220 495 792 924 792 495 220 66 12 1
1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1
1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1
1 15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105 15 1
1 16 120 560 1820 4368 8008 11440 12870 11440 8008 4368 1820 560 120 16 1
1 17 136 680 2380 6188 12376 19448 24310 24310 19448 12376 6188 2380 680 136 17 1
1 18 153 816 3060 8568 18564 31824 43758 48620 43758 31824 18564 8568 3060 816 153 18 1
1 19 171 969 3876 11628 27132 50388 75582 92378 92378 75582 50388 27132 11628 3876 969 171 19 1
1 20 190 1140 4845 15504 38760 77520 125970 167960 184756 167960 125970 77520 38760 15504 4845 1140 190 20 1
X|Y [ i ] = C（ n - (x-1)*i - 1 , i-1 ）;
https://www.cnblogs.com/sciorz/p/8904234.html
http://www.cnblogs.com/lemon-jade/p/8909462.html
#include
using namespace std;
typedef long long ll;
const ll MAXN = 1e6+7,mod=1e9+7;
ll fac[MAXN+100],inv[MAXN+100];
ll qpow(ll a,ll b){ll ans=1;while(b){if(b&1){ans=(ans*a)%mod;}a=(a*a)%mod;b>>=1;}return ans;
}
void init()
{fac[0]=1;for (int i=1; i< MAXN ; i++){fac[i] = (fac[i-1] * i )% mod;}inv[MAXN-1]=qpow(fac[MAXN-1],mod-2);for(int i=MAXN-2;i>=0;i--){inv[i]=inv[i+1]*(i+1)%mod;}
}
ll C(ll n, ll m)
{if ( n 本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！