LUOGU P3048 [USACO12FEB]牛的IDCow IDs(组合数)

解题思路

　　组合数学。首先肯定是要先枚举位数，假如枚举到第\(i\)位。我们可以把第一位固定，然后那么后面的随意放\(1\)，个数就为\(C_{i-1}^{k-1}\)。然后每次枚举时如果方案\(>n\)就说明位数为\(i\)，否则就让\(n-C_{i-1}^{k-1}\)，然后继续枚举下去。这样的话我们就确定了第一位，后面的位其实和数位\(dp\)里试填法的思路差不多，就是看\(n\)是否大于当前位为\(0\)时后面的方案数，如果大就把这一位设为\(1\)，然后减掉方案。算组合数有一个小\(trick\)就是先用分子约一个分母里比较大的，因为这道题\(k<=10\)，所以约完后暴力乘是不会炸\(long long\)的。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<cstdlib>

using namespace std;

const int MAXN = 1005;

typedef long long LL;

int n,k,ans[1000005];

inline LL C(int x,int y){

	if(x<y) return 0;

	if(!y) return 0;if(x==y) return 1;

	int lim=max(y,x-y),c=min(y,x-y);

	LL ret=1;

	for(register int i=x;i>=lim+1;i--)

		ret=ret*i;

	for(register int i=2;i<=c;i++)

		ret=ret/i;

	return ret;

}

int main(){

	scanf("%d%d",&n,&k);

	if(n==1) {while(k--) putchar('1');putchar('\n');return 0;}

	if(k==1) {putchar('1');n--;while(n--) putchar('0');putchar('\n');return 0;}

	n--;int l=k+1;

	while(C(l-1,k-1)<=n){

		n-=C(l-1,k-1);l++;

	}

	ans[1]=1;int res=k-1;putchar('1');

	for(register int i=2;i<=l;i++){

		LL te=C(l-i,res);

		if(n>te && res) {ans[i]=1;n-=te;res--;}

		putchar(ans[i]+'0');

	}putchar('\n');

	return 0;

}

巴特西

LUOGU P3048 [USACO12FEB]牛的IDCow IDs(组合数)

解题思路

代码

最新文章

热门文章