Print a 1337-string... - Educational Codeforces Round 70 div2 d

#文字列 #math

考えたこと

11...133...377...7
を考える
3 の数を x とすると, 3 は 2 つ選ぶので {}_x C _2
答えは, 1 の数を i, 7 の数を j とすると, i * {}_x C _2 * j

{}_x C _2が n 以下になる最大の x は, 10^5 くらい
全探索

このようなやり方では, n が大きな素数のとき詰む

s ≤ 10^5 より

よって, 11... 133...377...711...133...377...7 などを考える
足し算によって, 小さく分解したい
出来るだけ簡単な形で

簡単な例を考える
13371337
後ろの 7 に対して 33, 33
{}_r C _2

前の 7 に対して 33
1 通り

合計 6 + 1 = 7 通り

解法 (editorial)

13377...733...37
77...7 に対して 33 が substring の構成要素になりうる \ \ \ \ (1)
後ろの 7 に対して 33, 33...3 が substring の構成要素になりうる \ \ \ \ (2)


3 の数をすべてで x とする
(2) に関して, substring の個数は, \frac{x(x - 1)}{2}

(1) に関して, substring の個数は, 77...7 の 7 の個数 rem
rem = n - \frac{x(x - 1)}{2}