“新智认知”杯上海高校程序设计竞赛暨第十七届上海大学程序设计春季联赛----F-CSL的神奇序列

本文主要是介绍“新智认知”杯上海高校程序设计竞赛暨第十七届上海大学程序设计春季联赛----F-CSL的神奇序列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

首先发出题目链接：
链接：https://ac.nowcoder.com/acm/contest/551/F
来源：牛客网
涉及：打表

题目如下：

对于这种题，一般都是在草稿纸上找规律，找到了规律，代码就OK了

首先说一说这么高大上的题目表达的什么意思：

$\sum_{k=0}^{n}a_{k}a_{n-k}=w^{2}$
这个公式用中文理解起来就是，从k=0到k=n的所有a_k与a_n-k乘积的和等于w²这个常数。
（比如当n=3时， $\sum_{k=0}^{n}a_{k}a_{n-k}(n=3)=a_{0}a_{3}+a_{1}a_{2}+a_{2}a_{1}+a_{3}a_{0}=w^{2}$
，又如当n=2时， $\sum_{k=0}^{n}a_{k}a_{n-k}(n=2)=a_{0}a_{2}+a_{1}a_{1}+a_{2}a_{0}=w^{2}$ ）

懂了公式的意思，就可以开始找规律了，我们首先知道了a₀=w，而且n只能为正整数，不仅如此，题目还有爱的告诉我们序列是唯一的。

所以
当n=1时，得到方程式 $w*a_{1}+a_{1}*w=w^{2}$ ，解得 $a_{1}=\frac{w}{2}$
当n=2时，得到方程式 $w*a_{2}+\frac{w}{2}*\frac{w}{2}+a_{2}*w=w^{2}$ ，解得 $a_{2}=\frac{3w}{8}$
当n=3时，得到方程式 $w*a_{3}+\frac{w}{2}*\frac{3w}{8}+\frac{3w}{8}*\frac{w}{2}+a_{3}*w=w^{2}$ ，解得 $a_{3}=\frac{5w}{16}$
·
·

三个数据压根找不到规律，但是题目说为了让我们不难受，只让我们输出 $2^{n}n!$ 倍的a_n，那么可以找到 $2^{n}n!$ 倍a_n的规律

下面表格是部分数值
(其中 $b_{n}=2^{n}n! * a_{n}$ )：

n	$a_{n}$	$b_{n}$	$b_{n}$ 与 $b_{n-1}$ 的关系
1	$\frac{w}{2}$	$w$	-----
2	$\frac{3w}{8}$	$3 w$	$b_{n}=3b_{n-1}$
3	$\frac{5w}{16}$	$15 w$	$b_{n}=5b_{n-1}$
4	$\frac{35w}{128}$	$105 w$	$b_{n}=7b_{n-1}$
5	$\frac{63w}{256}$	$945 w$	$b_{n}=9b_{n-1}$

通过以上表格，可以通过不完全归纳法得到数列 $b_{n}$ 的递推式（这个也可以用数学归纳法求证）：

$b_{n+1}=[(2n-1)(b_{n}　mod　998244353)]　mod　998244353$ 且 $b_{1}=w$

有了递推关系，可以把数据范围了所有的 $b_{n}$ 存到数组 $b$ 里面，然后直接拿出来用就可以了！

代码如下：

#include <iostream>
#define mod 998244353//取模值
#define size 1000005//数组b大小
using namespace std;
typedef long long ll;
ll b[size];
int w,q,t;//w，q均为题目中的变量，t是每次访问数组输入的值
void getb(ll b[]){//通过递推式得到数组bfor(int i=1;i<=1e6;i++)b[i+1]=(b[i]%mod*(2*i+1))%mod;//递推式
}
int main(){cin>>w>>q;b[1]=w;//初始条件getb(b);//得到数组bwhile(q--){scanf("%d",&t);printf("%lld\n",b[t]);//访问数组b}return 0;
}