【BZOJ1951】[SDOI2010]古代猪文

题面

bzoj

洛谷

题解

题目实际上是要求

$ G^{\sum d|n\;C_n^d}\;mod \; 999911659 $

而这个奇怪的模数实际上是个素数，由欧拉定理

$ G^{\sum d|n\;C_n^d}\;mod \; 999911659=G^{\sum d|n\;C_n^d\;mod\;99911658}\;mod \; 999911659 $

主要是解决

$ \sum d|n\;C_n^d\;mod\;999911658 $

注意到

$ 999911658=2×3×4679×35617 $

所以可以对每个质因数枚举约束，用$Lucas$求组合数

最后$CRT$合并即可，注意要特判

代码

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

using namespace std;

typedef long long ll;

const ll Mod = 999911658;

ll N, G, fac[50005], ans[10], b[10] = {0, 2, 3, 4679, 35617};

ll fpow(ll x, ll y, ll p) {

	ll res = 1;

	while (y) {

		if (y & 1ll) res = res * x % p;

		x = x * x % p;

		y >>= 1ll;

	}

	return res;

}

void init (ll p) { fac[0] = 1; for (ll i = 1; i <= p; i++) fac[i] = i * fac[i - 1] % p; }

ll C(ll n, ll m, ll p) {

	if (n < m) return 0;

	return fac[n] * fpow(fac[m], p - 2, p) % p * fpow(fac[n - m], p - 2, p) % p;

}

ll Lucas(ll n, ll m, ll p) {

	if (!m || !n) return 1;

	return Lucas(n / p, m / p, p) * C(n % p, m % p, p) % p;

}

ll CRT() {

	ll res = 0;

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

		res = (res +

			   ans[i] * (Mod / b[i]) % Mod *

			   fpow(Mod / b[i], b[i] - 2, b[i])

			   % Mod) % Mod;

	return res;

}

int main () {

	cin >> N >> G;

	if (G % (Mod + 1) == 0) return puts("0") & 0;

	for (int p = 1; p <= 4; p++) {

		init(b[p]);

		for (int i = 1; i * i <= N; i++) {

			if (N % i == 0) {

				ans[p] = (ans[p] + Lucas(N, i, b[p])) % b[p];

				if (i * i != N) ans[p] = (ans[p] + Lucas(N, N / i, b[p])) % b[p];

			}

		}

	}

	printf("%lld\n", fpow(G, CRT(), Mod + 1));

	return 0;

}

巴特西

【BZOJ1951】[SDOI2010]古代猪文

【BZOJ1951】[SDOI2010]古代猪文

题面

题解

最新文章

热门文章