纯数学题，竟然交了4次……

设刚好满足n=k*(k+1)/2 也就是说满的。

那么有k层，因为可以左右走动,所以对于一个点来说可以由上一层的所有节点走过来（可以间接地通过本层过来），k-1到k有2*(k-1)条边。

设f(k)表示第k层一个走到其中一个点的种数，每层的所有点f(k)是一样的。

那么

f(k)=f(k-1)*(k-1)*2 => f(k)/f(k-1)=(k-1)*2

f(k)/f(k-1)=(k-1)*2

f(k-1)/f(k-2)=(k-2)*2

...

f(2)/f(1)=1*2

累乘=>f(k)=2^(k-1)*(k-1)!

满的话，k层有k个点，所以ans=f(k)*k=2^(k-1)*k!

那么不满的话？

就在满k层的基础上加上多出来的m个点。

k层到不满的k+1层有(2*m-1)条边，m个点。

=>ans=2^(k-1)*k!*m*(2*m-1)

m,k怎么算？ 你可以用公式，或者

while (k+1)*(k+2)

Accepted 有效得分：100 有效耗时：0ms

---|---|---|---|---|---|begin---|---|---|--

此题我是用从下往上推的★很有规律

example ：

0

0 0

0 0 0

0 0

最后一行的 结点数为s2=2; 每一个结点的路径数为 ns2;

∵最后一行的每一个本身有一种路径再加上任意两点之间互相传递

∴ns2:=s2;

各结点的 ns2 再往上推 再乘 第几个行 （同意行的任意两点之间互相传递）

___|\__|\__|\__|\__|__

最好自己画个图推一下就很容易理解了

___|\__|\__|_end.\___|\__|\__|_

10亿首歌????

orz !!

唱不死啊???????????

我承认我的弱小。。

找规律找了半天。。下面说说我的规律：

很显然，这道题应该采取递推的思路，也就是从塔尖往塔底推。

我的规律是这样找的，对于每一格，先考虑只能往左走上上走，故每一格的状态应由上方的n-1总数f(n-1)*(n-1)加上本格左边那个的状态总数g(n,i-1)，故g(n,i)=g(n,i-1)+f(n-1)*(n-1)。于是开始手算，发现第n行最末尾与第n-1行最末尾有递推关系:f(n)=f(n-1)*2*(n-1)，累推得f(n)=2^(n-1)*(n-1)!。故当n层被填满时，总共的状态应当是ans=n*f(n)=2^(n-1)*n!。下面考虑n层未填满时的状态。设第n层只有k个，则ans=k*sigma(g(n,i),i

看看我动态规划方程哪错了

cass4

g表示第i行最两边的一个位置从上一层(i-1层)来的最大值,g表示中间的一个位置从i-1层来的最大值.

则 有g=2*g+(i-1-2)*g;

　　g=2*(2*g+(i-1-2)*g);

对哦，可以推出递推式的....

可是不是DP的题目吗.....

要int64，要不就错了

递推式

太强大了

对于路人甲疑问的补充：那写标程干什么？~

program dyh(input,output);

var

k,t,s:qword;

n,i:longint;

procedure print(b:qword);

begin

if b=10)and(b=100)and(b=1000)and(b

ff

我又忘了用 long long 了.

大概这题想让我们矩阵DP吧。。。但是规律有点。。

water

手动模拟到第6层

规律显而易见

注意：找到规律的同志们切记

每做一步都要mod 70207一下

orz陶文博神牛

首先我们想到了将路径倒过来：从塔尖向塔底走。

由于不能走重复的点，于是我们考虑到每一层的入点与出点决定了这一层的走法，我们只要考虑往下走的情况：

对于这样一层，其点数为k，易知其下面一层的点数为p＝min{k+1,l}(l表示减去已经计算过的层中的点数以后剩下的点数)，往左的下法有min{k,p}种，往右的下法有min{k,p-1}种，我们只需将每一层的(min{k,p}+min{k,p-1})乘起来即可。

由于题目要求取模，我们不用写高精。

时间：O(n^0.5)

空间：O(1)

Orz楼下

仔细一看是个简单题，一遍AC了……

可以当作数塔来看，f:=f+f

最后一行f[n,i]=最后一行剩下的个数

但由于左右可以走，所以每行的总情况数是一样的，都是这行f的总和。

所以关键代码：

for j:=1 to i do

sum:=sum+f,f;

for j:=1 to i do

f:=sum;

这个就可以换成陶神牛的公式了

P.s 第一次忘补0了，囧

多谢curimit神牛教诲！

如对本题有疑问可以参看我的题解：http://xujieqi.blog.hexun.com/35722312_d.html