十字の操作ではなく行or列を選んで1色に塗る、という操作で作れるグリッドの個数を考えてみます。
\(dp_{h, w}\) = \(h\)行\(w\)列のグリッドの塗り分け方の個数
とします。
操作を逆から見ていきます。操作を行える箇所について包除をすることを考えると以下のような遷移が立ちます。
\[dp_{h, w} = \sum_{1 \leq i \leq h} (-1)^{i-1} C^i \binom{h}{i} dp_{h - i, w} + \sum_{1 \leq j \leq w} (-1)^{j-1} C^j \binom{w}{j} dp_{h, w -j} + \sum_{1 \leq i \leq h, 1 \leq j \leq w} (-1)^{i + j - 1} C \binom{h}{i} \binom{w}{j} dp_{h - i, w - j}\]
この式をそのまま計算すると4乗になって厳しいですが 3番目の項は \(\sum_{1 \leq i \leq h} (-1)^i \binom{h}{i} dp_{h - i, j}\) を各 \((h, j)\) で前計算しておけば 3乗で計算できます。
元の問題に戻ります。
最後の手の十字の操作が行えればあとは上で計算したものから答えを求めることができます。
これも操作可能な場所についての包除を行うことで計算できます。
初手の包除の立式について詳細を書く
or
or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up
Syntax | Example | Reference | |
---|---|---|---|
# Header | Header | 基本排版 | |
- Unordered List |
|
||
1. Ordered List |
|
||
- [ ] Todo List |
|
||
> Blockquote | Blockquote |
||
**Bold font** | Bold font | ||
*Italics font* | Italics font | ||
~~Strikethrough~~ | |||
19^th^ | 19th | ||
H~2~O | H2O | ||
++Inserted text++ | Inserted text | ||
==Marked text== | Marked text | ||
[link text](https:// "title") | Link | ||
 | Image | ||
`Code` | Code |
在筆記中貼入程式碼 | |
```javascript var i = 0; ``` |
|
||
:smile: | ![]() |
Emoji list | |
{%youtube youtube_id %} | Externals | ||
$L^aT_eX$ | LaTeX | ||
:::info This is a alert area. ::: |
This is a alert area. |
On a scale of 0-10, how likely is it that you would recommend HackMD to your friends, family or business associates?
Please give us some advice and help us improve HackMD.
Do you want to remove this version name and description?
Syncing