没看题解A的第一道多项式题…开心qwq
还是一遍A的
$$ \text{直接考虑卢卡斯定理。} \\ \text{首先考虑求出来模}p\text{为0的方案数。} \\ \text{设}n\text{的}p\text{进制下为}n_1n_2….n_k \\ \left( \begin{array}{c} x\\ n\\ \end{array} \right) =\left( \begin{array}{c} x_1\\ n_1\\ \end{array} \right) \left( \begin{array}{c} x_2\\ n_2\\ \end{array} \right) …\left( \begin{array}{c} x_k\\ n_k\\ \end{array} \right) \\ \text{显然如果存在任意}x_i<n_i,\text{则}\left( \begin{array}{c} x\\ n\\ \end{array} \right) =0\left( \text{mod }p \right) \\ \text{设}f\left( n,k \right) \text{表示考虑低}n\text{位，是否卡中}x\text{的上界时的结果多项式。} \\ \text{令}g\text{为模}p\text{意义下的原根，这个多项式的}i\text{次项的意义是选定的组合数在模}p\text{意义下为}g^i\text{的方案数。} \\ f\left( -\text{1,}true \right) =f\left( -\text{1,}false \right) =1 \\ \text{对于}i\ge \text{0,}f\left( i,false \right) =\left( \sum_{n_i\le k\le p-1}{x^y\left( \text{其中}g^y=\left( \begin{array}{c} k\\ n_i\\ \end{array} \right) \,\,\text{mod }p \right)} \right) f\left( i-\text{1,}false \right) \\ f\left( i,true \right) =x^y\left( \text{其中}g^y=\left( \begin{array}{c} x_i\\ n_i\\ \end{array} \right) \text{mod }p \right) f\left( i-\text{1,}true \right) +\left( \sum_{n_i\le k\le x_i-1}{x^y\left( \text{其中}g^y=\left( \begin{array}{c} k\\ n_i\\ \end{array} \right) \,\,\text{mod }p \right)} \right) f\left( i-\text{1,}false \right) \\ \text{所有卷积均为指数模}\varphi \left( p \right) \text{意义下的循环卷积。} \\ \text{最终}f\left( \lceil \log _px \rceil ,true \right) \text{即为结果多项式，}k\text{次项前的系数表示使得}\left( \begin{array}{c} x\\ n\\ \end{array} \right) =g^k\text{的方案数}\left( \text{不包括}0 \right) \text{。} \\ \text{复杂度}O\left( p\log p\log r \right) \\ \\ $$
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <vector>
using int_t = long long int;
using lint_t = __int128;
using std::cin;
using std::cout;
using std::endl;
const int_t mod = 998244353;
const int_t g0 = 3;
const int_t LARGE = 1 << 16;
int revs[17][LARGE];
//模p意义下的某个数对应的原根的指数
int_t map[LARGE];
int_t fact[LARGE];
std::vector<int_t> ndiv;
int_t p, g, phi;
lint_t n;
int_t power(int_t base, int_t index, int_t mod = ::mod);
void transform(int_t* A, int_t len, int_t arg);
template <class T>
void read(T& x) {
x = 0;
auto chr = getchar();
while (isdigit(chr) == false) {
chr = getchar();
}
while (isdigit(chr)) {
x = x * 10 + chr - '0';
chr = getchar();
}
}
int_t bitRev(int_t x, int_t len) {
int_t result = 0;
for (int i = 1; i < len; i++) {
result |= (x & 1);
x >>= 1;
result <<= 1;
}
return result | (x & 1);
}
int_t upper2n(int_t x) {
int_t result = 1;
while (result < x) result *= 2;
return result;
}
void poly_mul(const int_t* A, const int_t* B, int_t* C) {
static int_t Ax[LARGE], Bx[LARGE];
std::copy(A, A + p, Ax);
std::copy(B, B + p, Bx);
#ifdef DEBUG
cout << "mul " << endl;
for (int i = 0; i < p; i++) cout << A[i] << " ";
cout << endl;
for (int i = 0; i < p; i++) cout << B[i] << " ";
cout << endl;
#endif
int_t size2 = upper2n(2 * p);
for (int_t i = p; i < size2; i++) Ax[i] = Bx[i] = 0;
transform(Ax, size2, 1);
transform(Bx, size2, 1);
for (int_t i = 0; i < size2; i++) Ax[i] = Ax[i] * Bx[i] % mod;
transform(Ax, size2, -1);
#ifdef DEBUG
cout << "mul got ";
for (int i = 0; i < size2; i++)
cout << Ax[i] * power(size2, -1) % mod << " ";
cout << endl;
#endif
for (int_t i = phi; i < size2; i++) {
Ax[i % phi] = (Ax[i % phi] + Ax[i]) % mod;
}
const auto inv = power(size2, -1, mod);
#ifdef DEBUG
cout << "C = ";
#endif
for (int_t i = 0; i < phi; i++) {
C[i] = Ax[i] * inv % mod;
#ifdef DEBUG
cout << C[i] << " ";
#endif
}
}
const int_t OFFSET = 1;
std::vector<int_t> div(lint_t x) {
std::vector<int_t> result;
while (x) {
result.push_back(x % p);
x /= p;
}
return result;
}
int_t C(int_t n, int_t m) {
return ((fact[n] - fact[m] - fact[n - m]) % phi + phi) % phi;
}
void process(lint_t x, int_t* output) {
static int_t dp[103][2][LARGE];
memset(dp, 0, sizeof(dp));
dp[-1 + OFFSET][0][0] = dp[-1 + OFFSET][1][0] = 1;
auto xdiv = div(x);
int_t size = std::max(xdiv.size(), ndiv.size()) + 1;
xdiv.resize(size);
ndiv.resize(size);
for (int_t i = 0; i < size; i++) {
// false
{
static int_t poly[LARGE];
std::fill(poly, poly + p, 0);
for (int_t j = ndiv[i]; j <= p - 1; j++) {
poly[C(j, ndiv[i])] += 1;
}
poly_mul(poly, dp[i - 1 + OFFSET][0], dp[i + OFFSET][0]);
}
// true
{
auto& curr = dp[i + OFFSET][1];
static int_t poly[LARGE], output[LARGE];
std::fill(poly, poly + p, 0);
for (int_t j = ndiv[i]; j <= xdiv[i] - 1; j++)
poly[C(j, ndiv[i])] += 1;
poly_mul(poly, dp[i - 1 + OFFSET][0], output);
std::fill(poly, poly + p, 0);
for (int j = 0; j < phi; j++) curr[j] = (curr[j] + output[j]) % mod;
if (xdiv[i] >= ndiv[i]) poly[C(xdiv[i], ndiv[i])] += 1;
poly_mul(poly, dp[i - 1 + OFFSET][1], output);
for (int j = 0; j < phi; j++) curr[j] = (curr[j] + output[j]) % mod;
}
}
int_t zero = x % mod;
for (int i = 0; i < phi; i++) {
int_t x = power(g, i, p);
output[x] = (output[x] + dp[size - 1 + OFFSET][1][i]) % mod;
zero = (zero - dp[size - 1 + OFFSET][1][i] + mod) % mod;
}
output[0] = zero;
}
int main() {
for (int i = 1; i <= 16; i++) {
for (int j = 0; j < (1 << i); j++) {
revs[i][j] = bitRev(j, i);
}
}
lint_t left, right;
read(p);
read(n);
read(left);
read(right);
phi = p - 1;
ndiv = div(n);
std::vector<int_t> divisors;
for (int_t i = 2; i * i <= phi; i++) {
if (phi % i == 0) {
divisors.push_back(i);
if (i * i != phi) divisors.push_back(phi / i);
}
}
for (g = 2; g <= p - 1; g++) {
bool ok = true;
for (int_t x : divisors) {
if (power(g, x, p) == 1 && x != phi) {
ok = false;
break;
}
}
if (ok) {
break;
}
}
for (int i = 0; i < phi; i++) map[power(g, i, p)] = i;
for (int_t i = 2; i < p; i++) fact[i] = (fact[i - 1] + map[i]) % phi;
static int_t rights[LARGE], lefts[LARGE];
process(right, rights);
process(left - 1, lefts);
for (int i = 0; i < p; i++) {
printf("%lld\n", (rights[i] - lefts[i] + mod) % mod);
}
return 0;
}
void transform(int_t* A, int_t len, int_t arg) {
int_t size2 = log2(len);
for (int i = 0; i < len; i++) {
int x = revs[size2][i];
if (x > i) std::swap(A[i], A[x]);
}
for (int i = 2; i <= len; i *= 2) {
int_t mr = power(g0, arg * (mod - 1) / i, mod);
for (int_t j = 0; j < len; j += i) {
int_t curr = 1;
for (int_t k = 0; k < i / 2; k++) {
int_t u = A[j + k], t = A[j + k + i / 2] * curr % mod;
A[j + k] = (u + t) % mod;
A[j + k + i / 2] = (u - t + mod) % mod;
curr = curr * mr % mod;
}
}
}
}
int_t power(int_t base, int_t index, int_t mod) {
int_t result = 1;
if (index < 0) index = (index % (mod - 1) + mod - 1) % (mod - 1);
while (index) {
if (index & 1) result = result * base % mod;
base = base * base % mod;
index >>= 1;
}
return result;
}
发表回复