牛客挑战赛33 B 鸽天的放鸽序列

链接：https://ac.nowcoder.com/acm/contest/1115/B
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 524288K，其他语言1048576K
64bit IO Format: %lld

题目描述

擅长放鸽子的鸽天要确定自己的放鸽序列。放鸽序列是一个长度为n的01序列，表示接下来n天的是否放鸽。众所周知，鸽天是很喜欢鸽的，所以它想得到放鸽天数最多的序列并计数。

放鸽序列有一个奇怪的要求，由于这个要求太奇怪了，所以接下来是一句话题：

定义一个长为n的01序列

输入描述:

输入一行两个数

输出描述:

输出一个数，表示答案。

示例1

输入

复制

5 3

输出

复制

思路：

这道题用到了Lucas定理，不过没看懂，设计了数论的知识，实在不会。

不过思路还是有的，我就简单的讲解一下思路，以后遇到这类问题就套这个板子好了

题意：有长度为n的序列，这个序列中只有0或是1，现在问有k个1并且能权值最大的序列有多少个

样例 5 3

11100

10110

10011

现在要求权值最大，所以第一个数一定是1，然后对k的奇偶做了不同情况的处理：

当k为奇数时，那么减去第一个1，就变成了偶数，然后权值最大

我们是把两个1捆绑在一起，因为第一个数为1，假设后面有1 的话，那么从后面这个1开始Aj的求和%2后全为0，所以要两个1捆绑在一起，这样就迅速抵消了i往后扩展的影响

当k为偶数时，减去第一个1，那么k变成了奇数，于是为了使权值最大，那么必须有一个1放在这个序列的最后，为什么呢？因为这个k为偶数，我们必须要有偶数个1，那么只要最后一个1的位置越往后，前面都是奇数个1，那么权值就会最大，于是最后的位置就只能使这个序列的最后一个位置。

然后问题就变得简单多了。

就变成n个1，m个0的排列组合，不过因为n和m个数据范围很大，所以就要用到数论里面的东西，不是很会。

代码：

#include<iostream>
#include<stdio.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
ll pow(ll a,ll  b){
    ll res = 1;
    for(;b;b>>=1){
        if(b&1) res = res*a%mod;
        a = a*a%mod;
    }
    return res;
}
int main(){
    int n,k;
    scanf("%d%d",&n,&k);
    if(k%2==0){
        n--;
        k--;
    }
    n--;k--;
    ll x = k/2,N = n-k/2,ans = 1,base = 1;
    for(ll i=1;i<=x;i++){
        ans = ans*(N-i+1)%mod;
        base  = base*i%mod;
    }
    printf("%lld
",ans*pow(base,mod-2)%mod);
    return 0;
}