专栏文章

题解：P14461 【MX-S10-T2】『FeOI-4』青年晚报

rrenjiLD
P14461题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minbwzs7
此快照首次捕获于
2025/12/01 23:53
3 个月前
此快照最后确认于
2025/12/01 23:53
3 个月前
查看原文

P14461 【MX-S10-T2】『FeOI-4』青年晚报 题解

题目大意

给定两个初始的 mm 次多项式 F0(x)F_0(x) 和 G0(x)G_0(x)，以及递推关系：
Fi(x)=Gi−1(x)+Gi−1′(x)Gi(x)=Fi−1(x)−Fi−1′(x)\begin{aligned} F_i(x) &= G_{i-1}(x) + G_{i-1}'(x) \\ G_i(x) &= F_{i-1}(x) - F_{i-1}'(x) \end{aligned}
求经过 nn 次递推后的 Fn(x)F_n(x) 和 Gn(x)G_n(x) 的各项系数，结果对 109+710^9+7 取模。

解题思路

关键观察

通过分析递推关系，我们发现每两次递推构成一个循环：
Fn(x)=Fn−2(x)−Fn−2′′(x)Gn(x)=Gn−2(x)−Gn−2′′(x)\begin{aligned} F_n(x) &= F_{n-2}(x) - F_{n-2}''(x) \\ G_n(x) &= G_{n-2}(x) - G_{n-2}''(x) \end{aligned}
这意味着我们可以将问题分为奇偶两种情况处理。

数学推导

设 Fn(x)=∑i=0man,ixiF_n(x) = \sum_{i=0}^m a_{n,i} x^i，Gn(x)=∑i=0mbn,ixiG_n(x) = \sum_{i=0}^m b_{n,i} x^i。
经过数学推导，我们得到：
当 nn 为偶数时（n=2kn = 2k）：
a2k,i=∑j=0⌊(m−i)/2⌋(−1)j(kj)⋅(i+2j)!i!⋅a0,i+2jb2k,i=∑j=0⌊(m−i)/2⌋(−1)j(kj)⋅(i+2j)!i!⋅b0,i+2j\begin{aligned} a_{2k,i} &= \sum_{j=0}^{\lfloor (m-i)/2 \rfloor} (-1)^j \binom{k}{j} \cdot \frac{(i+2j)!}{i!} \cdot a_{0,i+2j} \\ b_{2k,i} &= \sum_{j=0}^{\lfloor (m-i)/2 \rfloor} (-1)^j \binom{k}{j} \cdot \frac{(i+2j)!}{i!} \cdot b_{0,i+2j} \end{aligned}
当 nn 为奇数时（n=2k+1n = 2k+1）：
a2k+1,i=∑j=0⌊(m−i)/2⌋(−1)j(kj)[(i+2j)!i!b0,i+2j+(i+2j+1)!i!b0,i+2j+1]b2k+1,i=∑j=0⌊(m−i)/2⌋(−1)j(kj)[(i+2j)!i!a0,i+2j−(i+2j+1)!i!a0,i+2j+1]\begin{aligned} a_{2k+1,i} &= \sum_{j=0}^{\lfloor (m-i)/2 \rfloor} (-1)^j \binom{k}{j} \left[ \frac{(i+2j)!}{i!} b_{0,i+2j} + \frac{(i+2j+1)!}{i!} b_{0,i+2j+1} \right] \\ b_{2k+1,i} &= \sum_{j=0}^{\lfloor (m-i)/2 \rfloor} (-1)^j \binom{k}{j} \left[ \frac{(i+2j)!}{i!} a_{0,i+2j} - \frac{(i+2j+1)!}{i!} a_{0,i+2j+1} \right] \end{aligned}

复杂度

  • 时间复杂度：O(m2)O(m^2)
  • 空间复杂度：O(m)O(m)

代码实现

CPP
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9 + 7;
const int N = 5100;

int n, m;
int f[N], g[N], F[N], G[N];
int fac[N], facinv[N], inv[N];

// 模运算优化函数
void add(int &x, int y) {
	x += y;
	if (x >= mod) x -= mod;
	if (x < 0) x += mod;
}
void mul(int &x, int y) {
	x *= y;
	if (x >= mod) x %= mod;
}
void sub(int &x, int y) {
	x -= y;
	if (x < 0) x += mod;
	if (x >= mod) x -= mod;
}

// 快速幂
int qp(int a, int b) {
	int res = 1;
	while (b) {
		if (b & 1) res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}

// 预处理阶乘和逆元
void init() {
	fac[0] = facinv[0] = inv[1] = 1;
	for (int i = 2; i < N; i++) inv[i] = (mod - mod / i) * inv[mod % i] % mod;
	for (int i = 1; i < N; i++) {
		fac[i] = fac[i - 1] * i % mod;
		facinv[i] = facinv[i - 1] * inv[i] % mod;
	}
}

// 计算组合数 C(n,m)
int C(int n, int m) {
	if (m < 0 || m > n) return 0;
	int res = 1;
	for (int i = 0; i < m; i++) mul(res, n - i);
	mul(res, facinv[m]);
	return res;
}

int val[N];

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> n >> m;
	init();
	for (int i = 0; i <= m; i++) cin >> f[i];
	for (int i = 0; i <= m; i++) cin >> g[i];

	if (n & 1) {
		// 奇数情况: n = 2k+1
		int k = (n - 1) / 2;
		for (int i = 0; i <= m / 2; i++)
			val[i] = (i & 1) == 0 ? C(k, i) : -C(k, i);

		for (int i = 0; i <= m; i++) {
			int sumf = 0, sumg = 0;
			for (int j = 0; i + 2 * j <= m; j++) {
				int tp1 = i + 2 * j, tp2 = i + 2 * j + 1;
				if (tp1 <= m) {
					add(sumf, val[j] * fac[tp1] % mod * facinv[i] % mod *
								  g[tp1] % mod);
					add(sumg, val[j] * fac[tp1] % mod * facinv[i] % mod *
								  f[tp1] % mod);
				}
				if (tp2 <= m) {
					add(sumf, val[j] * fac[tp2] % mod * facinv[i] % mod *
								  g[tp2] % mod);
					sub(sumg, val[j] * fac[tp2] % mod * facinv[i] % mod *
								  f[tp2] % mod);
				}
			}
			F[i] = sumf;
			G[i] = sumg;
		}
	} else {
		// 偶数情况: n = 2k
		int k = n / 2;
		for (int i = 0; i <= m / 2; i++)
			val[i] = (i & 1) == 0 ? C(k, i) : -C(k, i);

		for (int i = 0; i <= m; i++) {
			int sumf = 0, sumg = 0;
			for (int j = 0; i + 2 * j <= m; j++) {
				int tp = i + 2 * j;
				add(sumf,
					val[j] * fac[tp] % mod * facinv[i] % mod * f[tp] % mod);
				add(sumg,
					val[j] * fac[tp] % mod * facinv[i] % mod * g[tp] % mod);
			}
			F[i] = sumf;
			G[i] = sumg;
		}
	}

	for (int i = 0; i <= m; i++) cout << F[i] << ' ';
	cout << '\n';
	for (int i = 0; i <= m; i++) cout << G[i] << ' ';
	cout << '\n';

	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...