[ZJOI2010] 정렬 개수

좋은 문제, 실제가 무더기의 종수라는 것을 알아차리고 조합수를 잊어버렸다.

/**

 * Problem:Magic

 * Author:Shun Yao

 * Time:2013.6.2

 * Result:Accepted

 * Memo:DP, Math

 */



#include <cstdio>

#include <cmath>



const long Maxn = 1000005;



long min(long x, long y) {

	return x < y ? x : y;

}



long n;

long long p, f[Maxn], d[Maxn], jc[Maxn];



void exgcd(long long a, long long b, long long &x, long long &y) {

	if (!b) {

		x = 1;

		y = 0;

	} else {

		exgcd(b, a % b, y, x);

		y -= a / b * x;

	}

}



long long mulinv(long long X) {

	long long x, y;

	exgcd(X, p, x, y);

	return ((-x) / p * p + x + p) % p;

}



int main() {

	long i, dep, u, l, r;

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

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

	scanf("%ld%lld", &n, &p);

	jc[0] = 1;

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

		jc[i] = jc[i - 1] * i % p;

	f[0] = f[1] = d[0] = d[1] = 1 % p;

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

		dep = (long)(log(i) / log(2) + 1e-10);

		u = (long)(pow(2.0, dep) + 1e-10) - 1;

		l = ((u - 1) >> 1) + min(i - u, ((u + 1) >> 1));

		r = i - 1 - l;

		f[i] = f[l] * f[r] % p * jc[i - 1] % p;

		d[i] = d[l] * d[r] % p * jc[l] % p * jc[r] % p;

	}

	printf("%lld", f[n] * mulinv(d[n]) % p);

	fclose(stdin);

	fclose(stdout);

	return 0;

}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

JDBC 를 통 해 Oacle 데이터 베 이 스 를 연결 하 는 10 가지 기술

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

[ZJOI2010] 정렬 개수

좋은 웹페이지 즐겨찾기