问题 1726. -- 求长度为素数的路径个数

1726: 求长度为素数的路径个数

时间限制: 1 Sec  内存限制: 128 MB
提交: 8  解决: 7
[提交][状态][讨论版]

题目描述

对于正整数n （3≤n≤11），可以画出n阶的回形矩阵。下面画出的分别是3阶的，4阶的和7阶的回形矩阵：

1

1

1

1

2

1

1

1

1

n=3

1

1

1

1

1

2

2

1

1

2

2

1

1

1

1

1

n=4

1

1

1

1

1

1

1

1

2

2

2

2

2

1

1

2

3

3

3

2

1

1

2

3

4

3

2

1

1

2

3

3

3

2

1

1

2

2

2

2

2

1

1

1

1

1

1

1

1

n=7

对于n阶回形矩阵，从左上角出发，每步可以向右或向下走一格，走2*n-2步，可以到达右下角。我们把这样的路径上所有格子中的数值之和，叫做该路径的长度。

本题要求，对于给出n值，求出n阶回形矩阵有多少路径的长度为素数？

如n=3时，路径及长度有：

1

1

1

1

2

1

1

1

1

长度=5

1

1

1

1

2

1

1

1

1

长度=6

1

1

1

1

2

1

1

1

1

长度=6

1

1

1

1

2

1

1

1

1

长度=6

1

1

1

1

2

1

1

1

1

长度=6

1

1

1

1

2

1

1

1

1

长度=5







因此说，3阶回形矩阵有2条路径的长度为素数。

输入

 一个自然数n （3≤n≤11，不必判错）。

输出

一个正整数，即n阶回形矩阵中长度为素数的路径的个数。

样例输入

3

样例输出

2

提示

来源

江苏省第十届青少年信息学奥赛（小学组）

[提交][状态]