[ECUSTOJ#21]幂之和

Description

对于正整数$k$,可以定义$k$次方和
$$S _ { k } ( n ) = \sum _ { i = 1 } ^ { n } i ^ { k }$$
可以把它写成下面的形式,当$M$取最大可能的正整数时,所有的系数$a_i$都是确定的:
$$S _ { k } ( n ) = \frac { 1 } { M } \left( a _ { k + 1 } n ^ { k + 1 } + a _ { k } n ^ { k } + \ldots + a _ { 1 } n + a _ { 0 } \right)$$

现在给定整数$k$,输出$M , a _ { k + 1 } , a _ { k } , \dots , a _ { 1 } , a _ { 0 }$。$k \leq 20$

Solution

当然是Mathematica打表

表有点长,这里就不打了
这题的正解应该是拉格朗日插值
弄$k+1$个值出来然后带进去就ok
代码懒得敲了。。

0

[Codeforces 161E]Tetrahedron

Problem

一个正四面体顶点为$A,B,C,D$,从$D$出发,每走一步,更变当前所在顶点(不能保持不变),给定一个数$n$,求能有几种不同路径使得第$n$步走到$ D$。$1 \leq n \leq 10^7$

Solution

Method 1

当然是考虑递推辣
分两种情况:

  1. 第$ n-2 $步不在$ D$
  2. 第$ n-2 $步在$ D$

设$ a[n] $是第$ n $步到达$ D$的不同路径数。
对于 1 情况:第$ n-2 $步在$A,B,C$当中的一点,那么这时,在第$ n-1 $步能够到达$ D$,但其实他可以选择在第$ n-1 $到达另外两点,然后在第$ n $步到达$ D$,所以这种情况有$ 2a[n-1] $种。
对于 2 情况:第$ n-2 $步在$ D$点,那么他可以通过走到$A,B,C$中的任意一点,再回到$D$点,所以这种情况有$ 3a[n-2] $种。
故有$a[n]=2a[n-1]+3a[n-2]$

Method 2

特征方程!
优化至$O (\log n)$
Code:


通项公式:$a _ { n } = \frac { 3 } { 4 } \left( 3 ^ { n – 1 } – ( – 1 ) ^ { n – 1 } \right) ( n > 1 )$

Method 3

用$ dp[i][j] $表示第$ i $步走到$ j $点,则有:
$$dp[i][j]=dp[i][j]+dp[i-1][k]~~(j\ne{k})$$
于是从遍历$i,j,k$,最后取$ dp[n][3] $即可

Method 4

走$ n $步的总共不同路径有$3^{n}$条,若算出第$ n $点到达$ D $的概率,最后乘上$3^{n}$再取模即可。设$P_{n}(A)$为第$ n $步到达$A $点的概率,那么由对称性可知:$P_{n}(A)+P_{n}(B)+P_{n}(C)+P_{n}(D)=1$
又知$A,B,C$三点完全等价,故有$P_{n}(A)=P_{n}(B)=P_{n}(C)=\frac{1-P_{n}(D)}{3}$
然后又可知第$ n-1 $步必定在$A,B,C$当中一点,且无论在哪一点总有$\frac{1}{3} $的概率走到$D$,故有:
$$P_{n+1}(D)=\frac{1}{3}(P_{n}(A)+P_{n}(B)+P_{n}(C))=\frac{1-P_{n}(D)}{3}$$
结合$P_{1}(D)=0$可算出$P_{n}(D)$的表达式为:$3^{n}P_{n}(D)=\frac{3}{4}(3^{n-1}-(-1)^{n-1})$
跟递推的通项公式相同。

3+

一道算算算的数学竞赛题(滑稽)

昨晚lyj大佬扔给我一题(其实是他的某位学数竞的朋友扔给他的

题目是这样的:

若\( n \in \mathbb { N }\),证明\( (n+1)^4+n^5\)可以构成无穷多个合数。

一开始想偏了,暴力展开发现好像前面有个\(1\)变一下奇偶性后面只要为偶数就行了这不就证玩了吗傻逼题,后来发现是自己傻逼了,从原式子可以直接得出它一定是个奇数。

然后就开始想构造,事实上这个就很好办了:

我们设\(f(n)= (n+1)^4+n^5\),然后考虑\( f( n + k \cdot f(n) ), k \in \mathbb{N}\)

把它直接写成代数表达式的形式,也就是\(\left(k \left(n^5+(n+1)^4\right)+n\right)^5+\left(k \left(n^5+(n+1)^4\right)+n+1\right)^4\)

然后展开(Crazy!),得到\( k^5 n^{25}+5 k^5 n^{24}+30 k^5 n^{23}+120 k^5 n^{22}+425 k^5 n^{21}+1306 k^5 n^{20}+3520 k^5 n^{19}+8500 k^5 n^{18}+18440 k^5 n^{17}+36005 k^5 n^{16}+\\63474 k^5 n^{15}+100910 k^5 n^{14}+144070 k^5 n^{13}+183830 k^5 n^{12}+208120 k^5 n^{11}+206606 k^5 n^{10}+177060 k^5 n^9+128770 k^5 n^8+\\78120 k^5 n^7+38840 k^5 n^6+15509 k^5 n^5+4845 k^5 n^4+1140 k^5 n^3+190 k^5 n^2+20 k^5 n+k^5+5 k^4 n^{21}+21 k^4 n^{20}+\\114 k^4 n^{19}+402 k^4 n^{18}+1241 k^4 n^{17}+3333 k^4 n^{16}+7720 k^4 n^{15}+15800 k^4 n^{14}+28656 k^4 n^{13}+45716 k^4 n^{12}+64022 k^4 n^{11}+\\78282 k^4 n^{10}+82170 k^4 n^9+72270 k^4 n^8+51984 k^4 n^7+29916 k^4 n^6+13472 k^4 n^5+4620 k^4 n^4+1160 k^4 n^3+200 k^4 n^2+21 k^4 n+k^4+\\10 k^3 n^{17}+34 k^3 n^{16}+166 k^3 n^{15}+502 k^3 n^{14}+1312 k^3 n^{13}+2974 k^3 n^{12}+5680 k^3 n^{11}+9298 k^3 n^{10}+13132 k^3 n^9+15636 k^3 n^8+15246 k^3 n^7+11922 k^3 n^6+\\7360 k^3 n^5+3520 k^3 n^4+1264 k^3 n^3+322 k^3 n^2+52 k^3 n+4 k^3+10 k^2 n^{13}+26 k^2 n^{12}+114 k^2 n^{11}+284 k^2 n^{10}+600 k^2 n^9+\\1090 k^2 n^8+1600 k^2 n^7+1892 k^2 n^6+1804 k^2 n^5+1340 k^2 n^4+730 k^2 n^3+270 k^2 n^2+60 k^2 n+6 k^2+\\5 k n^9+9 k n^8+36 k n^7+70 k n^6+108 k n^5+145 k n^4+140 k n^3+84 k n^2+28 k n+4 k+n^5+n^4+4 n^3+6 n^2+4 n+1\)

然后怎么办!我们要证它可能是个合数,当然是给它除上一个东西…有经验的选手一看就知道是除以\(f(n)\)

于是我们得到了:

\(
\dfrac{f( n + k \cdot f(n) )}{f(n)} = k^5 n^{20}+4 k^5 n^{19}+22 k^5 n^{18}+76 k^5 n^{17}+233 k^5 n^{16}+620 k^5 n^{15}+1420 k^5 n^{14}+2876 k^5 n^{13}+\\5156 k^5 n^{12}+8112 k^5 n^{11}+11182 k^5 n^{10}+13420 k^5 n^9+13750 k^5 n^8+11704 k^5 n^7+8056 k^5 n^6+4372 k^5 n^5+\\1820 k^5 n^4+560 k^5 n^3+120 k^5 n^2+16 k^5 n+k^5+5 k^4 n^{16}+16 k^4 n^{15}+78 k^4 n^{14}+230 k^4 n^{13}+583 k^4 n^{12}+\\1293 k^4 n^{11}+2387 k^4 n^{10}+3745 k^4 n^9+5043 k^4 n^8+5616 k^4 n^7+4923 k^4 n^6+3270 k^4 n^5+1595 k^4 n^4+\\550 k^4 n^3+126 k^4 n^2+17 k^4 n+k^4+10 k^3 n^{12}+24 k^3 n^{11}+102 k^3 n^{10}+244 k^3 n^9+\\476 k^3 n^8+804 k^3 n^7+1076 k^3 n^6+1072 k^3 n^5+784 k^3 n^4+416 k^3 n^3+154 k^3 n^2+36 k^3 n+4 k^3+10 k^2 n^8+16 k^2 n^7+\\58 k^2 n^6+102 k^2 n^5+130 k^2 n^4+130 k^2 n^3+90 k^2 n^2+36 k^2 n+6 k^2+5 k n^4+4 k n^3+12 k n^2+12 k n+4 k+1
\)
希望你还没去世。我们已经得到了正确答案!

注意到这个结果里没有分式出现,所以把\(n,k\)的任意值代入结果都应为整数。于是就证明了\(f(n)\)是\( f( n + k \cdot f(n) )\)的一个因子,又由于\(f(n)\)单调递增,所以我们就可以按这个方法构造出无穷多个合数辣!!!

我觉得你真心需要一个Mathematica

1+