强行把两道不相关的题合到一起？不过还好，毕竟可以出到任意二阶递推数列（三阶的其实也可以，只要有人会解三次方程）
$$ \text{考虑第一部分：} \\ \sum_{1\le i\le n}{G\left( i,k \right)}=\sum_{1\le i\le n}{\left( \begin{array}{c} F_i\\ k\\ \end{array} \right) =\frac{1}{k!}\sum_{1\le i\le n}{F_i^{\underline{k}}}},\text{其中}F_i\text{为斐波那契数列,}F_0=\text{1,}F_1=1 \\ =\frac{1}{k!}\sum_{1\le i\le n}{\prod_{0\le j<k}{\left( F_i-i \right)}} \\ \text{构造}k\text{次多项式}H\left( x \right) =\prod_{0\le j<k}{\left( x-j \right)}=\sum_{0\le i\le k}{h_ix^i} \\ \text{则有}\sum_{1\le i\le n}{G\left( i,k \right)}=\frac{1}{k!}\sum_{1\le i\le n}{\sum_{0\le j\le k}{h_jF_{i}^{j}}} \\ =\frac{1}{k!}\sum_{0\le j\le k}{h_j\sum_{1\le i\le n}{F_{i}^{j}}} \\ \text{设}f\left( n,k \right) =\sum_{1\le i\le n}{F_{i}^{k}} \\ \text{由}F_i=\frac{5+\sqrt{5}}{10}\left( \frac{1+\sqrt{5}}{2} \right) ^n+\frac{5-\sqrt{5}}{10}\left( \frac{1-\sqrt{5}}{2} \right) ^n,\text{设}a=\frac{5+\sqrt{5}}{10},b=\frac{5-\sqrt{5}}{10} \\ x_1=\frac{1+\sqrt{5}}{2},x_2=\frac{1-\sqrt{5}}{2} \\ \text{则}F_i=ax_{1}^{n}+bx_{2}^{n} \\ \text{构造模意义下的数域}a+b\sqrt{5} \\ \text{则有}f\left( n,k \right) =\sum_{1\le i\le n}{F_{i}^{k}}=\sum_{1\le i\le n}{\left( ax_{1}^{i}+bx_{2}^{i} \right) ^k}=\sum_{1\le i\le n}{\sum_{0\le j\le k}{\left( \begin{array}{c} k\\ j\\ \end{array} \right) a^jx_{1}^{ij}b^{k-j}x_{2}^{i\left( k-j \right)}}} \\ =\sum_{0\le j\le k}{\left( \begin{array}{c} k\\ j\\ \end{array} \right) a^jb^{k-j}\sum_{1\le i\le n}{x_{1}^{ij}x_{2}^{i\left( k-j \right)}}} \\ =\sum_{0\le j\le k}{\left( \begin{array}{c} k\\ j\\ \end{array} \right) a^jb^{k-j}\sum_{1\le i\le n}{\left( x_{1}^{j}x_{2}^{k-j} \right) ^i}}=\sum_{0\le j\le k}{\left( \begin{array}{c} k\\ j\\ \end{array} \right) a^jb^{k-j}\frac{\left( x_{1}^{j}x_{2}^{k-j} \right) ^{n+1}-1}{x_{1}^{j}x_{2}^{k-j}-1}} \\ \text{第二个求和号等比数列求和即可。} \\ \text{第一部分复杂度}O\left( k^2\log k \right) \\ \text{考虑第二部分。} \\ \text{设}f\left( n \right) \text{表示长度为}n\text{的答案，打表可知} \\ f\left( 2n \right) =4f\left( 2n-2 \right) -f\left( 2n-4 \right) \\ \text{只考虑取偶数的}2n,\text{则}f\left( n \right) =4f\left( n-1 \right) -f\left( n-2 \right) \text{。} \\ \text{计算特征根}x_1=2+\sqrt{3},x_2=2-\sqrt{3} \\ \text{设}f\left( n \right) =ax_{1}^{n}+bx_{2}^{n},\text{由}f\left( 0 \right) =\text{1,}f\left( 1 \right) =\text{3得} \\ a=\frac{3+\sqrt{3}}{6},b=\frac{3-\sqrt{3}}{6} \\ \text{仍然像第一部分一样处理即可。} \\ $$
#include <assert.h>
#include <algorithm>
#include <cstring>
#include <iostream>
using int_t = long long int;
using std::cin;
using std::cout;
using std::endl;
const int_t mod = 998244353;
const int_t LARGE = 1000;
template <class T>
T power(T base, int_t index) {
base = (base % mod + mod) % mod;
T result = 1;
while (index) {
if (index & 1) result = result * base % mod;
index >>= 1;
base = base * base % mod;
}
return result;
}
template <int_t I>
struct Z {
int_t a = 0, b = 0;
Z(int_t a = 0, int_t b = 0) : a(a), b(b) {}
Z<I> operator+(const Z<I>& rhs) const {
return Z<I>{(a + rhs.a) % mod, (b + rhs.b) % mod};
}
Z<I> operator-(const Z<I>& rhs) const {
return Z<I>{(a - rhs.a + mod) % mod, (b - rhs.b + mod) % mod};
}
Z<I> operator*(const Z<I>& rhs) const {
return Z<I>{(a * (rhs.a % mod) % mod + I * b % mod * rhs.b % mod) % mod,
(a * rhs.b % mod + b * rhs.a % mod) % mod};
}
Z<I> inv() const {
int_t under = power(
(a * a % mod - I * b % mod * b % mod + I * mod) % mod, mod - 2);
return Z<I>{a * under % mod, (mod - b) * under % mod};
}
Z<I> operator/(const Z<I>& rhs) const { return (*this) * rhs.inv(); }
Z<I> operator%(int_t x) const { return Z<I>{a % x, b % x}; }
};
int_t fact[LARGE + 1], inv[LARGE + 1], factInv[LARGE + 1];
int_t C(int_t n, int_t m) {
return fact[n] * factInv[m] % mod * factInv[n - m] % mod;
}
template <int_t I>
Z<I> sumQ(Z<I> x, int_t n) {
if (x.a == 1 && x.b == 0) return n;
return (power(x, n) - 1) / (x - 1);
}
//求斐波那契数列的k次幂的前缀和
int_t sumF(int_t n, int_t k) {
if (k == 0) return n + 1;
using Z = ::Z<5>;
const Z a = Z(5, 1) / 10;
const Z b = Z(5, mod - 1) / 10;
const Z x1 = Z(1, 1) / 2, x2 = Z(1, mod - 1) / 2;
Z result = 0;
for (int_t i = 0; i <= k; i++) {
Z x = power(x1, i) * power(x2, k - i);
result =
result + power(a, i) * C(k, i) * power(b, k - i) * sumQ(x, n + 1);
}
assert(result.b == 0);
return result.a;
}
int_t sumG(int_t n, int_t k) {
if (k == 0) return n + 1;
using Z = ::Z<3>;
const Z a = Z(3, 1) / 6;
const Z b = Z(3, mod - 1) / 6;
const Z x1 = Z(2, 1), x2 = Z(2, mod - 1);
Z result = 0;
for (int_t i = 0; i <= k; i++) {
Z x = power(x1, i) * power(x2, k - i);
result =
result + power(a, i) * C(k, i) * power(b, k - i) * sumQ(x, n + 1);
}
assert(result.b == 0);
return result.a;
}
void poly_mul(const int_t* A, int_t n, const int_t* B, int_t m, int_t* C) {
static int_t Cx[LARGE * 2 + 1];
std::fill(Cx, Cx + n + m + 1, 0);
for (int_t i = 0; i <= n; i++)
for (int_t j = 0; j <= m; j++) {
Cx[i + j] = (Cx[i + j] + A[i] * B[j] % mod) % mod;
}
std::copy(Cx, Cx + n + m + 1, C);
}
int_t poly[LARGE + 1];
template <class Func>
int_t process(int_t n, int_t k, Func F) {
int_t result = 0;
for (int_t i = 0; i <= k; i++) {
result = (result + poly[i] * F(n, i) % mod) % mod;
}
result = result * factInv[k] % mod;
return result;
}
int main() {
fact[0] = fact[1] = factInv[0] = factInv[1] = inv[1] = 1;
for (int_t i = 2; i <= LARGE; i++) {
inv[i] = (mod - mod / i) * inv[mod % i] % mod;
fact[i] = fact[i - 1] * i % mod;
factInv[i] = factInv[i - 1] * inv[i] % mod;
}
int_t T, m, left, right, k;
cin >> T >> m >> left >> right >> k;
poly[0] = 1;
for (int_t i = 0; i < k; i++) {
int_t curr[] = {(mod - i) % mod, 1};
poly_mul(poly, k, curr, 1, poly);
}
if (m == 2) {
int_t result =
(process(right, k, sumF) - process(left - 1, k, sumF) + mod) % mod *
power(right - left + 1, mod - 2) % mod;
cout << result << endl;
} else {
int_t result = (process(right / 2, k, sumG) -
process((left - 1) / 2, k, sumG) + mod) %
mod * power(right - left + 1, mod - 2) % mod;
cout << result << endl;
}
return 0;
}
发表回复