問題一覧 > 通常問題

No.1561 connect x connect

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 7
作問者 : noya2noya2 / テスター : uwiuwi shinchanshinchan maspymaspy nok0nok0
1 ProblemId : 5518 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-04-24 19:31:39

問題文

$\ N\times M\ $のマス目があります。このマス目の、上から $i$ 番目の左から $j$ 番目のマスを$\ (i,\ j)\ $と呼ぶことにします。

はじめ、各マスに色は塗られていません。今から $1$ つ以上のマスを選んで黒に塗って $N\times M$ の大きさのポスターを作ります。

ここで、「映えるポスター」を以下のように定めます。

まず、 $1$ マスのみが黒に塗られたポスターは「映えるポスター」です。

$2$ マス以上が黒に塗られているとき、それらがすべて連結ならば、そのポスターは「映えるポスター」です。 すなわち、以下の条件を満たすものです。

  • 黒に塗られた任意の $2$ マスは、辺を共有するマスへの移動を繰り返し、黒に塗られたマスのみを通って互いに到達可能である

  • 「映えるポスター」が何通りあるかを求め、 $1000000007$ で割った余りを出力してください。

    ただし、 $2$ つのポスター$\ A,B\ $について、あるマス$\ (x,\ y)\ $が存在して、 $A$ のマス$\ (x,\ y)\ $と $B$ のマス$\ (x,\ y)\ $のうち一方のみが黒に塗られているとき、$\ A,B\ $は異なるものとします。

    制約

  • 入力はすべて整数
  • $1\le N \le 9$
  • $1\le M \le 10^{18}$
  • 入力

    $N\ M$
    

    出力

    「映えるポスター」が何通りあるかを求め、 $1000000007$ で割った余りを出力してください。

    最後に改行してください。

    サンプル

    サンプル1
    入力
    2 2
    出力
    13

    $2\times 2=4$ マスを $1$ つ以上塗る塗り方は $2^4-1=15$ 通りありますが、

    そのうち斜め $2$ マスだけが塗られたものは「映えるポスター」ではありません。これは図のように $2$ 通りあります。

    それ以外は「映えるポスター」ですから、 $15-2=13$ が答えとなります。

    サンプル2
    入力
    5 6
    出力
    45280509

    サンプル3
    入力
    7 77
    出力
    713420418

    $1000000007$ で割った余りを求めてください。

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