主題

ZeroJudge - g352: 函數的秘密 解題心得

Not In My Back Yard | 2021-09-28 00:00:04 | 巴幣 0 | 人氣 49

題目連結:


題目大意:
定義一函數 G(x) 代表著 x 於十進位中的開頭有幾個連續的 1。例如 G(123) = 1 、 G(1198) = 2 、 G(23432) = 0。

現在輸入第一列給定一正整數 X(1 ≦ X ≦ 1000),代表一正整數 N 的位數長。接著第二列給定 X 位數之數字,代表正整數 N 之數值。試問 G(1) + G(2) + …… + G(N) 之值為何?請將答案取 998244353 的餘數後輸出。



範例輸入:
範例輸入 #1
1
9

範例輸入 #2
2
12

範例輸入 #3
8
12345678


範例輸出:
範例輸出 #1
1

範例輸出 #2
5

範例輸出 #3
4691357


解題思維:
這種題目的核心精神很像,都是需要觀察然後利用排列組合來算出答案。

因為題目的函數 G 求的是數字最前面(左側)有幾個連續的 1 ,而我們是從 1 ~ N 每個數字都計算,可以看到其中的每個數字的位數不盡相同。因此我們可以稍微修改 G 的定義,使其變為:在忽略數字的前導零後有幾個連續的 1。例如 G(001) 於原本的定義是 0 而現在變為了 1、G(01121) 現在為 2 等等。這樣子我們便可以將 1 ~ N 中間的所有數字統一在前面補 0 使所有數字都統一為 X 位數長。

所以現在我們便可以討論每個位置的位數之「1」總共為所求貢獻多少,例如 N = 14 中有 01 、 11 這兩個數字貢獻了個位數的「1」、而有 10 、 11 、 12 、 13 、 14 這五個數字則貢獻了十位數的「1」。而為了方便,以下我們從左至右依序稱每一位數為第 1 、 2 、 3 、…… 、 X 位數。

現在我們來觀察一些範例:
N = 14 時:
14,可以看到第 1 位數允許有 1 開頭的數字,如 10 、 11 等,但是最大只能到 14。而 10 ~ 14 有 5 個數字,因此第 1 位數為所求貢獻了 5 這個值。注意這邊只算第 1 位數是「1」的有幾個數字,目前不含其他位數。

14,可以看到第 2 位數可以有 01 或是 11 開頭的數字,如 0111。因此第 2 位數貢獻了 2。

因此,所求為 5 + 2 = 7。



N = 1324 時:
1124,可以看到第 1 位數是「1」的會有 1 開頭的數字,如 1102 、 1073 、 1124 等。而 1000 ~ 1124 有 125 個數字,因此第 1 位數為所求貢獻了 125。

1124,可以看到第 2 位數是「1」的會有 0111 開頭的數字,如 0123 、 0100 、 1124 等。而 01 開頭有 100 個數字(0100 ~ 0199)、11 開頭則有 25 個數字(1100 ~ 1124),因此第 2 位數為所求貢獻了 125。

1124,可以看到第 3 位數是「1」的會有 001011111 開頭的數字。而這樣的數字有 30 個,因此第 3 位數為所求貢獻了 30。

1124,可以看到第 4 位數是「1」的會有 00010011 0111 1111 開頭的數字。而這樣的數字有 4 個,因此第 4 位數為所求貢獻了 4。

因此,所求為 125 + 125 + 30 + 4 = 284。



N = 10005 時:
10005,可以看到第 1 位數是「1」的會有 1 開頭的數字。而這樣的數字有 6 個。因此第 1 位數為所求貢獻了 6。

10005,可以看到第 2 位數是「1」的只會有 01 開頭的數字(因為 N 前兩位數為 10,而 10 < 11 所以無法以 11 開頭)。而這樣的數字有 1000 個。因此第 2 位數為所求貢獻了 1000。

10005,可以看到第 3 位數是「1」的只會有 001 011 開頭的數字(同上,不會出現 111 開頭的)。而這樣的數字有 200 個。因此第 3 位數為所求貢獻了 200。

10005,可以看到第 4 位數是「1」的有 0001 0011 0111 開頭的數字。而這樣的數字有 30 個。因此第 4 位數為所求貢獻了 30。

10005,可以看到第 5 位數是「1」的有 00001 00011 00111 01111 開頭的數字。而這樣的數字有 4 個。因此第 5 位數為所求貢獻了 4。

因此,所求為 6 + 1000 + 200 + 30 + 4 = 1240。



由上面三個例子我們可以看到,從 N 的第 1 位數掃到第 X 位數。對於第 i 位數我們窮舉 0……001、0……011 等這些長度 i 位數的數字來跟 N 的前 i 位數來比大小。當目前窮舉的開頭大過 N 的前 i 位數則代表該開頭不可能出現,也因此無法貢獻於所求(參見 N = 10005 第 2 位數發生之例子)。

而且當窮舉出來的開頭 < N 的前 i 位數時,該開頭將會貢獻 10 ^ (X - i);而當開頭與前 i 位數大小相同時,則會貢獻 C + 1。其中 C 為 N 的第 i + 1 位數(含)到結尾的整個值(參見 N = 1124 第二位數之 11 開頭之事例)。

最後將每位數的每個可能開頭所貢獻之值加總,並取除以 998244353 的餘數即是所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作