You are given two integers nn and mm . Calculate the number of pairs of arrays (a,b)(a,b) such that:
- the length of both arrays is equal to mm ;
- each element of each array is an integer between 11 and nn (inclusive);
- ai≤biai≤bi for any index ii from 11 to mm ;
- array aa is sorted in non-descending order;
- array bb is sorted in non-ascending order.
As the result can be very large, you should print it modulo 109+7109+7 .
Input
The only line contains two integers nn and mm (1≤n≤10001≤n≤1000 , 1≤m≤101≤m≤10 ).
Output
Print one integer – the number of arrays aa and bb satisfying the conditions described above modulo 109+7109+7 .
ExamplesInput
2 2
Output
5
Input
10 1
Output
55
Input
723 9
Output
157557417由题意可知,这个题所求的两个序列实际上可以合并成一个,将递增序列的头部接到递减序列的尾部,所得一个长为2m的序列。原问题可以转化为求范围1到n的2m个数组成的递增序列的个数(一个序列里可以有两个重复的数)。官方题解直接用Python+组合数公式
from math import factorial as fact
mod = 10**9 + 7def C(n, k):
return fact(n) // (fact(k) * fact(n - k))n, m = map(int, input().split())
print(C(n + 2*m - 1, 2*m) % mod)
从原理入手,当这2m个数里有i个数不相同时,先从n个位置里用C(n,i)算出当前有几种选法,接下来有2m-i个数是和刚刚选出来的序列的部分数相同,可以看作同球入不同盒问题直接应用公式计算即可,每次循环更新ans。题目要求取模,这里借鉴了https://www.csdn.net/gather_2b/NtzaIgxsNzQtYmxvZwO0O0OO0O0O.html里组合数快速取模的知识。
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
long long n,m;
int inv(int a)
{
return a==?:(long long)(MOD-MOD/a)*inv(MOD%a)%MOD;
}
long long C(long long n,long long m)//组合数快速取模
{
if(m<)return ;
if(n<m)return ;
if(m>n-m)m=n-m;
long long up=,down=;
long long i;
for(i=;i<m;i++)
{
up=up*(n-i)%MOD;
down=down*(i+)%MOD;
}
return up*inv(down)%MOD;
}
int main()
{
cin>>n>>m;
int i;
long long ans=;
for(i=*m;i>=;i--)//有i个不同的数
{
if(i>n)continue;
ans=(ans+C(n,i)*/*同球入不同盒 2*m-i入i */ C(*m-i+i-,i-))%MOD;
}
printf("%lld",ans);
return ;
}