题目描述
脑筋急转弯
由于 ai≤bi,结合 a 递增 b 递减的要求,只要满足 $a_m≤b_m$ 就满足 $a_i≤b_i$。
于是我们完全可以把 b 倒过来拼在 a 的后面,这样题目就简化成了求长为 2m,元素范围在 $[1,n]$ 的非严格单调递增数组个数。
这是一个经典组合数学问题,等价于把 2m个无区别的球放入 n 个有区别$(因为数组有顺序)$的盒子中,且允许空盒的方案数,这里第 i 个盒子放的球就表示值为 $i$ 的元素。
我们采用隔板法来解决:把 n 个盒子当做 n−1 个隔板,球加上隔板总共有 2m+n−1 个位置,从中选择 n−1 个位置放隔板,这样就把 2m 个球划分成了 n 份,放入对应的盒子中。
因此方案数为 $C_{2m+n−1}^{n−1}$。
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 100010, mod = 1e9 + 7;
//利用快速幂与费马小定理
int fact[N], infact[N];
int qmi(int a, int k, int p)
{
int res = 1;
while (k)
{
if (k & 1) res = (LL)res * a % p;
a = (LL)a * a % p;
k >>= 1;
}
return res;
}
int main()
{
fact[0] = infact[0] = 1;
for (int i = 1; i < N; i ++ )
{
fact[i] = (LL)fact[i - 1] * i % mod;
infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;//利用快速幂求逆元
}
int n,m,a,b;
scanf("%d%d", &n, &m);
a=2*m+n-1,b=n-1;
printf("%d\n", (LL)fact[a] * infact[b] % mod * infact[a - b] % mod);//随时取模,防止溢出
return 0;
}
我的代码:
# include [HTML_REMOVED]
using namespace std;
const int M=1e9+7;
int n,m;
int c(int a,int b)
{
int res=1;
for(int i=a,j=1;j<=b;i–,j++)
{
res=res*i/j%M;
if(res>n) break;
}
return res;
}
int main()
{
cin>>n>>m;
cout<<c(2*m+n-1,n-1);
return 0;
}
为什么错?
(输入10 1 输出11 标准答案55)
第一行是标准库。
在取模的意义下除会失效要改成乘上逆元,C(a,b)==a!/b!/(a-b)!,你这个组合数好像也求错了
刚刚试了一下你的组合数那里去掉break还有/改成乘逆元就可以过了;
#include [HTML_REMOVED]
#include [HTML_REMOVED]
#include [HTML_REMOVED]
#include[HTML_REMOVED]
using namespace std;
const int M=1e9+7;
int n,m;
int qmi(int a, int k, int p) // 求a^k mod p
{
int res = 1 % p;
while (k)
{
if (k & 1) res = (long long)res * a % p;
a = (long long)a * a % p;
k >>= 1;
}
return res;
}
int c(int a,int b)
{
int res=1;
for(int i=a,j=1;j<=b;i–,j++)
{
res=(long long)resi%Mqmi(j,M-2,M)%M;
}
return res;
}
int main()
{
cin>>n>>m;
cout<<c(2*m+n-1,n-1);
return 0;
}
谢谢!!
这份题解和灵茶山艾府大佬的好像啊……
太妙了 orz