【数学】奶牛编号（jzoj 2932）_综合

奶牛编号

jozj 2932

题目大意

求出有m个1的01串中字典序第n大的字典序

输入样例

7 3

输出样例

数据范围

$1 \leqslant M \leqslant 10$
$1 \leqslant N \leqslant 10^7$

解题思路

我们先从01串长度入手：
先对 $m = 1$ 的特判
然后 $m \geqslant 2$ 的我们用组合数来判断当前位是否为1（详情见代码）

代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
ll n, m, a, b, p;
int main()
{scanf("%lld%lld", &n, &m);if (m == 1)//特判{printf("1");for (int i = 1; i < n; ++i)printf("0");return 0;}for (ll i = 5000; i > 0; --i)//C_(5000,2)>10^7，已经足够了if (!m) printf("0");else{a = b = 1;//c_(i,m)就是这一位是0的组合数for (ll j = m; j > 1; --j)//组合数公式的分母部分b *= j;for (ll j = i; j > i - m && a / b < n; --j)//分子部分，a/b<n是防止数据过大a *= j;if (a / b < n)//如果这一位是1那n就比C_(i,m)大{printf("1");m--;n -= a / b;p = 1;}else if (p) printf("0");}if (m) printf("1");else printf("0");return 0;
}