題目連結：
題目大意：
定義一函數 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 開頭的數字，如 01 和 11。因此第 2 位數貢獻了 2。
因此，所求為 5 + 2 = 7。
N = 1324 時：
1124，可以看到第 1 位數是「1」的會有 1 開頭的數字，如 1102 、 1073 、 1124 等。而 1000 ～ 1124 有 125 個數字，因此第 1 位數為所求貢獻了 125。
1124，可以看到第 2 位數是「1」的會有 01 、 11 開頭的數字，如 0123 、 0100 、 1124 等。而 01 開頭有 100 個數字（0100 ～ 0199）、11 開頭則有 25 個數字（1100 ～ 1124），因此第 2 位數為所求貢獻了 125。
1124，可以看到第 3 位數是「1」的會有 001 、 011 、 111 開頭的數字。而這樣的數字有 30 個，因此第 3 位數為所求貢獻了 30。
1124，可以看到第 4 位數是「1」的會有 0001、0011 、 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 的餘數即是所求。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人
