AT_tenka1_2013_final_a 天下一有無

[problemUrl]: https://atcoder.jp/contests/tenka1-2013-final/tasks/tenka1_2013_final_a 天下一株式会社では、天下一級の物質「Tenkaitium」を製造している。 「Tenkaitium」は、次世代量子コンピューターの製造に欠かせない物質となっている。 新人のユウヤ君は、「Tenkaitium」の運用・管理チームに配属されることになった。 配属されてからのユウヤ君の初仕事は、運搬のため、容器に「Tenkaitium」を入れる作業をすることになった。しかし、「Tenkaitium」には、ある一定量以上が接近すると「Tenkanitium」に変化してしまうという特性がある。残念ながら「Tenkanitium」に産業的価値はない。 そこで、ユウヤ君は、容器を $ N\ \times\ M $のマスに区切り、「Tenkaitium」が同じマスに2つ以上入ったり、縦、横、ななめに隣り合あったマスに入ったりしないように配置することを考えた。 「Tenkaitium」を縦、横、ななめに隣り合わないように1つ以上配置する方法が何通りあるかを $ {\rm\ mod}\ 1000000007 $ で標準出力に1行で出力せよ。ただし、回転や反転によって同じになる配置も別々のものとする。 また、行の終端には改行が必要である。 ``` 2 2 ``` ``` 4 ``` 「Tenkaitium」が有るマスを■、無いマスを□とすると以下の $ 4 $ 通りの配置が考えられる。 draw_grid( "1000", 2, 2 ); draw_grid( "0100", 2, 2 ); draw_grid( "0010", 2, 2 ); draw_grid( "0001", 2, 2 ); ``` 3 2 ``` ``` 10 ``` 以下の $ 10 $ 通りの配置が考えられる。 draw_grid( "100000", 3, 2 ); draw_grid( "010000", 3, 2 ); draw_grid( "001000", 3, 2 ); draw_grid( "000100", 3, 2 ); draw_grid( "000010", 3, 2 ); draw_grid( "000001", 3, 2 ); draw_grid( "101000", 3, 2 ); draw_grid( "100001", 3, 2 ); draw_grid( "001100", 3, 2 ); draw_grid( "000101", 3, 2 );

N/A

N/A