这个题的原是BZOJ4402

这个题他说元素相同的排列算同一种

所以说我们只需要统计字典序最小的就好

不超过m和不超过n这个两个限制不够强，所以我们先按照一定为n和m做，然后枚举n,m就好

然后我们观察排列

发现是从这样一个序列之中加东西

1,2,3,...,m

or

1,2,3,...,m,m-1

每个相邻的数之间可以加数，且每次需加偶数个

这个的答案就是C((n+m)\2-1,m-1-1)+C((n+m-1)\2-1,m-1-1)

然后我们记ans(m)为一定要有m这个数的序列的答案

$ans(m)=\sum^{(n-m)/2}_{i=0} C(i+m-1,m-1-1)+\sum^{(n-m-1)/2}_{i=0} C(i+m-1-1,m-1-1)$

然后最终答案就是$\sum^m_1 ans(i)$

然后这里放个公式

$\sum^{n}_{i=0}C(i+m-1,m-1)=C(n+m,m)$

然后就做完了

这里放个链接题解

这篇题解讲的挺明白的，可以看看

code

#include <bits/stdc++.h>
using namespace std;

const long long p = 1e9 + 7;

const long long N = 2e6 + 10;

long long fac[N], inv[N], ans;

long long n, m;

void init(){
	fac[0] = inv[0] = inv[1] = 1;
	for(long long i = 1;i < N; i++){
		fac[i] = fac[i-1] * i % p;
	}
	for(long long i = 2;i < N; i++){
		inv[i] = (p - p / i) * inv[p % i] % p;
	}
	for(long long i = 1;i < N; i++){
		inv[i] = inv[i] * inv[i-1] % p;
	}
}

long long C(long long n,long long m){
	if(n < m) return 0;
	if(n < p && m < p) return fac[n] * inv[m] % p * inv[n-m] % p;
	return C(n/p,m/p) * C(n%p,m%p) % p;
}

void read(){
	cin >> n >> m;
}

void compute(){
	init();
	if(n && m) ans = 1;
	for(long long i = 2;i <= min(n,m); i++){
		ans = (ans + C((n-i)/2+i-1,i-1)) % p;
		if(n-i-1>=0) ans = (ans + C((n-i-1)/2+i-1,i-1)) % p; 
	}
	cout << ans; 
}

int main(){
	read();
	compute();
	return 0;
}