du熊填数字 Time Limit: 3000/2000 MS (C/Others) Memory Limit: 65536/32768 K (C/Others) & G- A7 M+ Y, ]4 x8 h0 c7 F# r
本次组委会推荐使用C、C++ Problem Description
. ]/ g4 Q _) R; V9 X0 p: m4 ^- z( Q
du熊这几天使劲的往一个n 行n列的矩阵填0和1这两个数字,n为偶数,而且矩阵由里向外分成了n / 2层。比如n = 6时,矩阵的分层如下:/ W z- b% h1 G @/ ]9 N
du熊填数时有一个要求:不能存在两个相邻的1,且位于不同的层(这里的相邻指两格子共用一条线)。
O0 Z' k, V. a/ w/ C2 q% L 请你帮du熊计算一下有多少种填法。
) _/ y t+ u5 lInput" R# t9 i3 x: A" F( j
9 p' J" o% ^2 Y6 `, _1 r# b# X2 s- Z6 f 输入包含多组测试数据,每组数据包含一个偶数n (2 <= n <= 500)。+ n9 d% ?, F! R( U
Output# o# a4 W! @6 t3 A: Q6 Y9 V
% D3 X8 c# ^' L 请计算并输出对2012取余后的结果。, r' G! [1 ~6 x6 x( \- X5 _3 A' G
: w) M- y- U, y
Sample Input+ C+ }& w. a) r) T N
! Y$ a) I$ b* X
2. g9 c( ^8 K2 M
4
4 l+ m0 v7 ?* _) ^8 P/ |Sample Output: y/ t6 f2 s0 C! T
16- l" l- }! M) P+ {: @8 F6 o- X
1952$ ?8 c8 X# v, O- p) o2 [
; _8 F; B% ?# D D6 O5 dHint
7 F3 S. O; o. a7 g* e当n = 4时: V# M* v w1 ~! L
8 l" j% C6 b0 W) Q g! \+ i; [1011) F/ e( Y0 d3 D- G) N
0100
2 Z+ j- |9 o( T% N0 b3 y0100& F# [% V6 c5 b+ M: j4 i
0000! l- i/ m$ n; G3 F! R, S, _$ z
是满足要求的9 C) w% i9 c1 ~& Y& F- g1 Q2 G" ]; `3 W
3 `% ]; ?- q; B
1111
$ i# s2 k1 j0 k- Z$ Q+ X2 V9 ?5 f# |0100
* d! S# V4 r, o& `4 ~% Q! u0100
; @1 @& E/ ^# q! m5 W0000
! G) E4 s- Y# |0 `# f8 m# Z是不满足要求的,因为第一行第二列的1和第二行第二列的1相邻且位于不同的层。
( s: H* P/ I5 ^2 u) u+ r) v, c
, J2 U* _# T5 L/ Q8 R2 z
6 G6 w' e7 r* z6 r3 O- B |