問題一覧 > 通常問題

No.1561 connect x connect

レベル : / AI推定難易度 : 2650 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 8
作問者 : noya2 / テスター : uwi shinchan maspy nok0
お気に入りにしたユーザー ProblemId : 5518 / 自分の提出
問題文最終更新日: 2021-04-24 19:31:39
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 301 (順位表) の他の問題:

Problem Statement

There is a grid of $\ N\times M\ $ cells. The cell in the $i$-th row from the top and the $j$-th column from the left is called $\ (i,\ j)\ $.

Initially, no cell is colored. You will now choose $1$ or more cells and paint them black to make a poster of size $N\times M$.

Here, an "attractive poster" is defined as follows.

First, a poster with only $1$ cell painted black is an "attractive poster".

When $2$ or more cells are painted black, the poster is an "attractive poster" if they are all connected. That is, it satisfies the following condition.

  • Any $2$ cells painted black can reach each other by repeatedly moving to a cell sharing an edge, passing only through cells painted black.

  • Find the number of "attractive posters" and output it modulo $1000000007$.

    Here, $2$ posters $\ A,B\ $ are considered different if there exists a cell $\ (x,\ y)\ $ such that exactly one of the cell $\ (x,\ y)\ $ of $A$ and the cell $\ (x,\ y)\ $ of $B$ is painted black; in that case, $\ A,B\ $ are different.

    Constraints

  • All inputs are integers.
  • $1\le N \le 9$
  • $1\le M \le 10^{18}$
  • Input

    $N\ M$
    

    Output

    Find the number of "attractive posters" and output it modulo $1000000007$.

    Print a newline at the end.

    Sample

    Sample 1
    Input
    2 2
    Output
    13

    There are $2^4-1=15$ ways to paint $1$ or more of the $2\times 2=4$ cells,

    but among them, those with only $2$ diagonal cells painted are not "attractive posters". There are $2$ such ways, as shown in the figure.

    All the others are "attractive posters", so the answer is $15-2=13$.

    Sample 2
    Input
    5 6
    Output
    45280509

    Sample 3
    Input
    7 77
    Output
    713420418

    Find the answer modulo $1000000007$.

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。