Рассмотрим произвольный хороший массив, поделим все его элементы на первый и уберем все повторяющиеся элементы. Получившийся массив назовём задающим, а все его префиксы недозадающими. $$$\newline$$$ Из задачи о шарах и перегородках, для задающего массива длины $$$m$$$ с последним элементом $$$x$$$, число хороших массивов, для которых он является задающим = $$$\lfloor \frac{c}{x} \rfloor * {n - 1 \choose m - 1}$$$ $$$\newline$$$ Тогда наивное решение — перебор всех задающих массивов $$$\newline$$$ Несложно понять, что для массива $$$a$$$ число хороших, для которых он будет недозадающим зависит только от его длины и последнего элемента, а именно $$$f(m, x) = \lfloor \frac{c}{x} \rfloor * {n - 1 \choose m - 1} + \sum\limits_{t = 2}^{\lfloor \frac{c}{x} \rfloor}f(m + 1, tx)$$$, где $$$f(m, x)$$$ — число хороших, для которых массив с длиной $$$m$$$ и последним элементом $$$x$$$ будет недозадающим. $$$\newline$$$ В таком случае мы можем оптимизировать перебор используя запомининие ответов, однако на время возникают проблемы с памятью $$$\newline$$$ Из формулы $$$f$$$ можно сказать, что $$$\forall x_1, x_2, \lfloor \frac{c}{x_1} \rfloor = \lfloor \frac{c}{x_2} \rfloor: f(m, x_1) = f(m, x_2)$$$. Тогда при подсчёте $$$f$$$ мы можем не просто перебирать все значения $$$t$$$, а объединять $$$t$$$ с одинаковыми значениями $$$\lfloor \frac{c}{xt} \rfloor$$$ $$$\newline$$$ Также это значит, что при запоминании ответов мы можем не все ответы сохранять в $$$f(m, x)$$$, а только те, в которых $$$x \leq \sqrt{c}$$$, а остальные сохранять в $$$g(m, \lfloor \frac{c}{x} \rfloor)$$$ $$$\newline$$$ P. S. Сложно посчитать ассимптотику решения, однако оно работает очень быстро: на тесте $$$n = c = 5 * 10^7$$$, оно работает за $$$296$$$ мс., а на тесте $$$n = c = 10^9$$$, оно работает за $$$2792$$$ мс., на больших тестах решение работает значительно дольше из-за нужды замены int на long long
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
const ll MOD = 998244353;
const ll LOGC = 31;
const ll SQRTC = 31600;
ll choose[LOGC];
ll pw(ll a, ll m) {
if (!m)
return 1;
a %= MOD;
if (m % 2)
return a * pw(a, m - 1) % MOD;
return pw(a * a, m / 2);
}
int f[LOGC][SQRTC];
int g[LOGC][SQRTC];
int brute_force(int n, int c, int x, int m) {
int cdivx = c / x;
if (x < SQRTC && f[m][x]) {
return f[m][x];
}
if (cdivx < SQRTC && g[m][cdivx]) {
return g[m][cdivx];
}
int ans = cdivx * choose[m - 1] % MOD;
if (m < n) {
for (int t = 2; t <= cdivx;) {
int cdivnx = c / (x * t);
int nx = t * x;
// aa - наибольшее число такое, что c / nx == (c / (nx + (aa - 1) * x))
ll aa = 1;
while ((nx + (2 * aa - 1) * x) * cdivnx <= c) {
aa *= 2;
}
for (ll t = aa; t > 0; t >>= 1) {
if ((nx + (aa + t - 1) * x) * cdivnx <= c)
aa += t;
}
ans += aa * brute_force(n, c, nx, m + 1) % MOD;
t += aa;
ans %= MOD;
}
}
if (x < SQRTC)
f[m][x] = ans;
if (cdivx < SQRTC)
g[m][cdivx] = ans;
return ans;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, c;
cin >> n >> c;
choose[0] = 1;
for (int i = 1; i < LOGC; ++i) {
choose[i] = choose[i - 1] * (n - i) % MOD * pw(i, MOD - 2) % MOD;
}
cout << brute_force(n, c, 1, 1) << endl;
}