题解 P4317 花神的数论题

并不难，但是因为各种 SB 原因调了 1145141919810min（悲

我们会发现 \(\operatorname{sum}\) 其实很小，顶多就 \(50\)，这启发我们统计每个 \(\operatorname{sum}\) 取值的数量。因此令 \(f_{i}\) 为满足 \(\operatorname{sum}(o) = i\) 的 \(o\) 的数量。

显而易见数位 dp 可以做。

//SIXIANG

#include <iostream>

#include <cstring>

#define MAXN 100000

#define int long long

#define QWQ cout << "QWQ" << endl;

using namespace std;

const int Mod = 10000000 + 7;

int qpow(int n, int m) {

	int res = 1;

	while(m) {

		if(m & 1) res = res * n % Mod;

		n = n * n % Mod, m >>= 1;

	}

	return res;

}

int f[200][50][2][2], tot, arr[MAXN + 10];

int pika(int i, int s, int limit, int lead, int num, int o) {

	if(!i) return (s == o);

	if(f[i][s][limit][lead] != -1) return f[i][s][limit][lead];

	int lim = ((limit) ? (arr[i]) : 1), rest = 0;

	for(int p = 0; p <= lim; p++)

		rest += pika(i - 1, s + (p == 1), limit && (p == arr[i]), lead && (!p), (num << 1) + p, o);

	f[i][s][limit][lead] = rest;

	return rest;

}

int solve(int x) {

	do {

		arr[++tot] = x % 2;

		x >>= 1;

	} while(x);

	int mul = 1;

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

		memset(f, -1, sizeof(f));

		int res = pika(tot, 0, 1, 1, 0, p);

		mul = mul * qpow(p, res) % Mod;

	}

	return mul;

}

signed main() {

	int n; cin >> n;

	cout << solve(n) << endl;

}

巴特西

题解 P4317 花神的数论题

最新文章

热门文章