2717 小Biu的序列

用N个不同的字符（编号1 - N），每种字符最多使用一次，组成一个字符串，有如下要求：
(1) 对于编号为i的字符，如果2 * i > n，则该字符可以作为结尾字符。如果不作为结尾字符而是中间的字符，则该字符后面可以接任意字符。
(2) 对于编号为i的字符，如果2 * i <= n，则该字符不可以作为结尾字符。作为中间字符，那么后面接的字符编号i一定要满足 2*i>n。
问有多少长度为M且符合条件的字符串，由于数据很大，只需要输出该数Mod 10^9 + 7的结果。

输入

输入2个数，N, M中间用空格分割，N为不同字符的数量，M为字符串的长度。(2 <= N, M <= 10^6)

输出

输出符合条件的字符串的数量。由于数据很大，只需要输出该数Mod 10^9 + 7的结果。

输入样例

3 3

输出样例

4

 解析：

      如果用k表示“前半段字符的个数”，那么n-k可以表示“后半段字符的个数”，下面我们考虑如何计数。

      设表示字符串时用到了t个“前半段字符”，先选出这t个字符，即C(k,t)。

      然后，考虑到 前半段字符后面必须是后半段字符 ，我们选出k个"后半段字符"任意放在刚才选出来的那t个”前半段字符“的后面，组成一组，即A(n-k,t)。

      这样，我们就有了t个组，然后再从剩下的”后半段字符“里挑出m-2*t个字符自成一组，即C(n-k-t,m-2*t)，然后我们就有了m-t个组，总共m个字符。
      最后，我们再把这m-t个组任意排序，即A(m-t,m-t).
      最终式子为  ΣC(k,t)*A(n-k,t)*C(n-k-t,m-2*t)*A(m-t,m-t)。

放代码：

#include <bits/stdc++.h>
#define ll long long
const ll M=1e9+7;
using namespace std;
ll fac[1000006]={1},n,m, ans;
ll pw(ll x,int ti=M-2){
    ll ret=1;
    while(ti){
        if(ti&1)ret=ret*x%M;
        ti>>=1;
        x=x*x%M;
    }
    return ret;
}
ll A(int a, int b){
	if(a<0||b<0)return 0;
    return fac[a]*pw(fac[a-b])%M;
}
ll C(int a, int b){
    return A(a,b)*pw(fac[b])%M;
}
int main() {
	for(int i=1; i<=1e6;i++)fac[i]=fac[i-1]*i%M;
	cin>>n>>m;
	ll k=n>>1, lt=max(m-n+k,0ll),rt=min(k,m/2);
	for(int t=lt;t<=rt;t++)
	    ans+=C(k,t)*A(n-k,t)%M*C(n-k-t,m-2*t)%M*A(m-t,m-t)%M,ans%=M;
	cout<<ans;
	return 0;
}