洛谷 P2518 [HAOI2010]计数 (组合数)

题面

题解

本来想练数位dp的,结果又忍不住写了组合数..

去掉一个\(0\)可以看作把\(0\)移到前面去

那么题目转化为 \(n\)有多少个排列小于\(n\)

强制某一位比\(n\)的对应位置上的数小, 后面方案组合数算一下即可

Code



#include<bits/stdc++.h>

#define LL long long

#define RG register

using namespace std;

template<class T> inline void read(T &x) {

	x = 0; RG char c = getchar(); bool f = 0;

	while (c != '-' && (c < '0' || c > '9')) c = getchar(); if (c == '-') c = getchar(), f = 1;

	while (c >= '0' && c <= '9') x = x*10+c-48, c = getchar();

	x = f ? -x : x;

	return ;

}

template<class T> inline void write(T x) {

	if (!x) {putchar(48);return ;}

	if (x < 0) x = -x, putchar('-');

	int len = -1, z[20]; while (x > 0) z[++len] = x%10, x /= 10;

	for (RG int i = len; i >= 0; i--) putchar(z[i]+48);return ;

}

char s[55];

int a[55], b[10], C[55][55];

int main() {

	//freopen(".in", "r", stdin);

	//freopen(".out", "w", stdout);

	scanf("%s", s);

	int n = strlen(s);

	for (int i = 0; i < n; i++)

		a[i+1] = s[i]-'0', b[a[i+1]]++;

	LL ans = 0;

	for (int i = 0; i <= n; i++) C[i][i] = 1, C[i][0] = 1;

	for (int i = 2; i <= n; i++)

		for (int j = 1; j < i; j++)

			C[i][j] = C[i-1][j-1]+C[i-1][j];

	for (int i = 1; i <= n; i++) {

		for (int j = 0; j < a[i]; j++)

			if (b[j] > 0) {

				LL s = 1;

				b[j]--;

				for (int k = 0, p = n-i; k < 10; p -= b[k++])

					s *= C[p][b[k]];

				b[j]++;

				ans += s;

			}

		b[a[i]]--;

	}

	write(ans);

	return 0;

}

巴特西

洛谷 P2518 [HAOI2010]计数 (组合数)

题面

题解

Code

最新文章

热门文章