題目
https://gmoj.net/senior/#main/show/6884
解法1
我用的是非題解做法——
S
L
S
6884
SLS_{6884}
SLS6884?差分法，
假設現在有一個填數方案
a
1
,
1
a
1
,
2
a
1
,
3
?
a
1
,
n
?
1
a
1
,
n
a
2
,
1
a
2
,
2
a
2
,
3
?
a
2
,
n
?
1
a
2
,
n
?
?
?
?
?
?
a
n
?
1
,
1
a
n
?
1
,
2
a
n
?
1
,
3
?
a
n
?
1
,
n
?
1
a
n
?
1
,
n
a
n
,
1
a
n
,
2
a
n
,
3
?
a
n
,
n
?
1
a
n
,
n
\begin{matrix} a_{1,1} & a_{1,2} & a_{1,3} &\cdots & a_{1,n-1} & a_{1,n}\\ a_{2,1} & a_{2,2} & a_{2,3} &\cdots & a_{2,n-1} & a_{2,n}\\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ a_{n-1,1} & a_{n-1,2} & a_{n-1,3} &\cdots & a_{n-1,n-1} & a_{n-1,n}\\ a_{n,1} & a_{n,2} & a_{n,3} &\cdots & a_{n,n-1} & a_{n,n} \end{matrix}
a1,1?a2,1??an?1,1?an,1??a1,2?a2,2??an?1,2?an,2??a1,3?a2,3??an?1,3?an,3????????a1,n?1?a2,n?1??an?1,n?1?an,n?1??a1,n?a2,n??an?1,n?an,n??
由于要求每種路徑上的
∑
a
\sum a
∑a不同，而且每一個
a
i
,
j
a_{i,j}
ai,j?的大小又有限制，就不妨規定從
a
1
,
1
a_{1,1}
a1,1?到
a
1
,
n
a_{1,n}
a1,n?再到
a
n
,
n
a_{n,n}
an,n?的路徑權值最小，為0；而從
a
1
,
1
a_{1,1}
a1,1?到
a
n
,
1
a_{n,1}
an,1?再到
a
n
,
n
a_{n,n}
an,n?的路徑權值最大，
這樣子勢必有圖2優于圖1，
考慮圖2比圖1優在哪里，將它們重合后，可以得到圖3：
在
(
2
,
1
)
→
(
4
,
3
)
(2,1)\to (4,3)
(2,1)→(4,3)的矩形中，綠色路徑更優；但是在
(
4
,
3
)
→
(
6
,
6
)
(4,3)\to (6,6)
(4,3)→(6,6)中，藍色路徑更優，且逆轉了綠色路徑的優勢，
為了方便表示一個矩形內一種路徑比另一種路徑優的值，我們可以令
b
i
,
j
=
a
i
+
1
,
j
?
a
i
,
j
+
1
b_{i,j}=a_{i+1,j}-a_{i,j+1}
bi,j?=ai+1,j??ai,j+1?，那么這時
(
2
,
1
)
→
(
4
,
3
)
(2,1)\to (4,3)
(2,1)→(4,3)的矩形中綠色路徑的優勢就為
b
2
,
1
+
b
3
,
1
+
b
2
,
2
+
b
3
,
2
b_{2,1}+b_{3,1}+b_{2,2}+b_{3,2}
b2,1?+b3,1?+b2,2?+b3,2?，
如果右下方的矩形縮小成只有4格（這是最小規格了，只包含一個
b
i
,
j
b_{i,j}
bi,j?），左上方的矩形無限擴大，也必須要滿足右下方的
b
b
b值大于左上方的
∑
b
\sum b
∑b，
因此可以得出
b
b
b要滿足的條件：
b
x
,
y
>
∑
i
=
1
x
?
1
∑
j
=
1
y
?
1
b
i
,
j
b_{x,y}>\sum_{i=1}^{x-1}\sum_{j=1}^{y-1}b_{i,j}
bx,y?>i=1∑x?1?j=1∑y?1?bi,j?
那現在就可以開始填b了：
- 因為數值要盡可能小，而 b > 0 b>0 b>0，第一行、第一列就全部填1了；
- 第二行也要盡可能小，但是要滿足上面的不等式，因此第二行從第二列開始填 2 , 3 , 4 , ? 2,3,4,\cdots 2,3,4,?；
- 第三行從第二列開始滿足不等式的最小填法是 3 , 6 , 10 , ? 3,6,10,\cdots 3,6,10,?；
- ……
那么就可以得出整個矩形
b
b
b了，以
n
=
7
n=7
n=7為例，它長成這樣：
1
1
1
1
1
1
1
2
3
4
5
6
1
3
6
10
15
21
1
4
10
20
35
56
1
6
21
56
126
252
\begin{matrix} 1 & 1 & 1 & 1 & 1 & 1\\ 1 & 2 & 3 & 4 & 5 & 6\\ 1 & 3 & 6 & 10 & 15 & 21 \\ 1 & 4 & 10 & 20 & 35 & 56\\ 1 & 6 & 21 & 56 & 126 & 252 \end{matrix}
11111?12346?1361021?14102056?151535126?162156252?
發現了什么沒有？
天哪！它是個斜著的楊輝三角形，我可以用組合數切掉這道題啦，哈哈哈……
楊輝三角形這個東西在本題沒什么用，
這個矩形滿足
b
i
,
j
=
b
i
?
1
,
j
+
b
i
,
j
?
1
b_{i,j}=b_{i-1,j}+b_{i,j-1}
bi,j?=bi?1,j?+bi,j?1?，因此直接遞推就可以了，
最后再求
a
a
a，
這種寫法還有一個好處——不用寫高精度減法，
解法2
其實沒有必要先求
b
b
b再求
a
a
a，這里介紹一種更為簡便的方法——
W
Y
D
6884
WYD_{6884}
WYD6884?填數法，
假設現在我們用某種渠道獲得了可以跑出
n
=
6
,
n
=
7
n=6,n=7
n=6,n=7的程式（暴力是不行的，但是正解可以），可以打表找規律，發現：
a
i
,
j
=
{
1
,
i
=
1
,
或
2
2
a
i
?
1
,
1
j
=
1
a
i
?
1
,
j
+
a
i
,
j
?
1
,
j
+
i
?
n
≤
0
a
i
?
1
,
j
+
a
i
,
j
?
1
?
a
i
+
j
?
n
,
n
?
1
,
j
+
i
?
n
>
0
a_{i,j}=\begin{cases} 1,&i=1,\text{或} 2\\ 2a_{i-1,1}& j=1\\ a_{i-1,j}+a_{i,j-1}, &j+i-n\le 0\\ a_{i-1,j}+a_{i,j-1}-a_{i+j-n,n-1}, &j+i-n> 0 \end{cases}
ai,j?=??????????1,2ai?1,1?ai?1,j?+ai,j?1?,ai?1,j?+ai,j?1??ai+j?n,n?1?,?i=1,或2j=1j+i?n≤0j+i?n>0?
這樣雖然要寫高精度減法，但是由于不用求
b
b
b，也很好打，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/226957.html
標籤：其他
上一篇：1451F Nullify The Matrix（博弈，異或）
下一篇：多年之后，開個新坑