p517.ans1
======================
2

=================
p517.in1
======================
4 4

=================
p517.py
======================
import sys

sys.set_int_max_str_digits(100000)


def main():
    # The problem is to count the number of ways to fill a grid of size n x m
    # with dominoes, with the constraint that no 4 dominoes share a corner. WLOG
    # assume that n < m. If n = 2, there is a simple DP solution - let dp[i] be
    # the number of ways to fill a 2 x i grid. We have two cases - we place one
    # vertical domino, or we place two horizontal dominoes followed by a vertical.
    # This is dp[i - 1] and dp[i - 3] respectively. We can't place more than two
    # horizontal dominoes as otherwise we would have 4 dominoes sharing a corner.
    #
    # If n > 2, we can use a similar DP approach, but we need to be careful. One
    # observation is that if we ever place two horizontal or vertical dominoes
    # next to each other, we can never place a third one next to them without
    # violating the corner constraint (note that n, m >= 3). Another observation
    # is that there are only two ways to cover a K x K grid with dominoes with the
    # corner constraint - we start with the top right corner and place it vertically
    # or horizontally. We can show that the domino to the left / below can't be
    # connected on the long side as otherwise we would have 4 dominoes sharing a
    # corner, because the rest of the grid is uniquely determined:
    #
    #          4 3 1 1
    #          4 3 2 2       -> middle dominoes create a "bad" corner.
    #          5 5 6 6
    #          7 7 8 8
    #
    # In other words, after choosing the top-right tile, the full composition of the grid
    # is uniquely determined (for fixed K x K grid). These two configurations are
    # effectively the same, but rotated by 90 degrees. For example the 6 x 6 grid:
    #
    #          1 3 3 9 9 E
    #          1 4 8 8 A E
    #          2 4 B C A H   -> This configuration is valid.
    #          2 6 B C G H
    #          5 6 D D G I
    #          5 7 7 F F I
    #
    # Let's solve n being even. We will have dp[i][0] meaning covering the first i
    # columns such that the last column is fully vertical, and dp[i][1] meaning the
    # last column is not fully vertical. Clearly, dp[i][0] = dp[i - 1][1] as we can't
    # have two adjacent columns fully vertical. Now we have two options for dp[i][1]:
    #
    #   1. We fully use the above horizontal construction, which can be done
    #      in dp[i - n][0] ways.
    #
    #   2. We use the above vertical construction, but only the middle n - 2 columns
    #      that don't contain the fully vertical columns. There are dp[i - n + 2][0]
    #      ways to do this (or dp[i - n + 1][1] using a similar argument).
    #
    # When n is odd, we can use a similar approach basing on the (n + 1) x (n + 1)
    # even construction. Essentially we can either place the n x (n + 1) pattern
    # without one of the fully horizontal rows, or we can try filling the n x n
    # grid without it's leftmost column, which can be done in a unique way too.
    # For this we don't need a two-dimensional DP, as it's impossible to have a fully
    # vertical column. Essentially, there is a unique way to go to dp[i - n + 1] and
    # dp[i - n - 1] from dp[i] up to the orientation of the topmost and rightmost tile.

    n, m = map(int, input().split())

    if n * m % 2 == 1:
        print(0)
        return

    if n > m:
        n, m = m, n

    if n == 1:
        print(1)
        return

    if n == 2:
        dp = [0] * (m + 1)
        dp[0] = 1
        dp[1] = 1
        dp[2] = 2
        for i in range(3, m + 1):
            dp[i] = dp[i - 1] + dp[i - 3]
        print(dp[m])
        return

    if n % 2 == 1:
        dp = [0] * (m + 1)
        dp[0] = 1
        for i in range(1, m + 1):
            for delta in [n - 1, n + 1]:
                if i - delta >= 0:
                    dp[i] += dp[i - delta]
        print(2 * dp[m])
        return

    dp = [[0, 0] for _ in range(m + 1)]
    dp[0][0] = 1
    dp[0][1] = 1

    for i in range(1, m + 1):
        dp[i][0] = dp[i - 1][1]
        for delta in [n - 2, n]:
            if i - delta >= 0:
                dp[i][1] += dp[i - delta][0]

    print(dp[m][0] + dp[m][1])


if __name__ == "__main__":
    main()

=================
statement.txt
======================
517. Cornerless Tiling
Time limit per test: 0.25 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard



An cornerless tiling of an mx n rectangle is such tiling of this rectangle with 1x 2 and 2x 1 dominoes that no four dominoes share a corner.

For example, here are the two possible cornerless tilings of 4x 4 square:


How many cornerless tilings of mx n rectangle are there?

Input
First and only line of the input file contains two integers m and n, 1 ≤ n, m ≤ 1000.

Output
In the only line of the output file write the sought number of tilings.

Example(s)
sample input
sample output
4 4
2

=================
