#	User	Rating
1	tourist	4009
2	jiangly	3831
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	gamegame	3386
10	ksun48	3373

#	User	Contrib.
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

About the problem

The problem is to calculate the number of such subsequence $$${a_1, a_2, \dots a_n}$$$ that ($$$a_1 + a_2 + \dots + a_k = n$$$) where ($$$k \geq 2$$$) and ($$$a_i \in {1, 2, \dots, n}$$$)

It is the sequence OEIS A111133

My approach for small n

Lets $$$magic(left, last)$$$ is the number of valid subsequences whose sum equal $$$left$$$ which next selected element is such $$$next$$$ in range $$$(last, left]$$$ ($$$next$$$ is strictly greater then last selected number $$$last$$$ and not greater than current sum $$$left$$$). The recursive stop when $$$left = 0$$$ then we found one valid subsequence

Recursive dp - O(n^3) - small n

vector<vector<ll> > f; /// init as -1
ll magic(int left = n, int last = 0)
{
    if (left == 0) return 1;

    ll &res = f[left][last];
    if (res != -1) return res;
    res = 0;

    for (int next = last + 1; next <= left; ++next)
        res += magic(left - cur, next);

    return res;
}

My approach for bigger n

Lets $$$magic(sum, cur)$$$ is the number of valid subsequences whose selected sum is $$$sum$$$ and current selecting element is $$$cur$$$

$$$cur$$$ is init as $$$1$$$ (smallest element) and recursive stop when it greater than $$$n$$$ (largest element)
$$$sum$$$ is in range $$$[0, n]$$$ when it equal $$$n$$$ then we found 1 valid subsequence so we return $$$1$$$, else if it greater than $$$n$$$ we stop the recursive

The complexity is still $$$O(n^3)$$$ which $$$O(n^2)$$$ calculation and $$$O(n)$$$ for bignum implementation

Recursive dp - O(n^3) - bignum result

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

#define all(x) (x).begin(), (x).end()
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef long long ll;

struct bignum {
    vector<int> d;
    bignum(int x = 0) {
        do d.push_back(x % 10);
        while (x /= 10);
    }

    void fix()
    {
        d.push_back(0);
        for (int i = 0; i + 1 < d.size(); ++i)
        {
            d[i + 1] += d[i] / 10; d[i] %= 10;
            if (d[i] < 0) { d[i + 1]--; d[i] += 10; }
        }
        while (d.size() >= 2 && d.back() == 0) d.pop_back();
    }

    void operator += (const bignum &a) {
        const vi &c = a.d;
        d.resize(max(c.size(), d.size()));
        for (int i = 0; i < c.size(); ++i) d[i] += c[i];
        fix();
    }

    void operator -= (const bignum &a) { 
        const vi &c = a.d;
        d.resize(max(c.size(), d.size()));
        for (int i = 0; i < c.size(); ++i) d[i] -= c[i];
        fix();
    }

    void out()   {  for (int i = int(d.size()) - 1; i >= 0; --i) cout << d[i]; }
    void outln() { out(); putchar('\n'); }
};

int n;
vector<vector<bignum> > f;
vector<vector<bool> > m;
bignum magic(int sum = 0, int cur = 1) {
    if (sum == n) return bignum({1});
    if (sum > n) return bignum({0});
    if (cur > n) return bignum({0});

    bignum &res = f[sum][cur];
    if (m[sum][cur]) return res; else m[sum][cur] = true;

    res += magic(sum + cur, cur + 1);
    res += magic(sum, cur + 1);
    
    return res;
}

int main()
{
    cin >> n;
    f.assign(n + 1, vector<bignum>(n + 1, bignum({0})));
    m.assign(n + 1, vector< bool >(n + 1, false));
    bignum res = trau();
    res -= bignum({1});
    res.outln();
}

Iterative dp - O(n^3) - bignum result

include

using namespace std;

define all(x) (x).begin(), (x).end()

typedef pair<int, int> pi; typedef vector vi; typedef long long ll;

struct bignum { vector d; bignum(int x = 0) { do d.push_back(x % 10); while (x /= 10); } bignum(const vi &a) { d = a; reverse(all(d)); }

void fix()
{
    d.push_back(0);
    for (int i = 0; i + 1 < d.size(); ++i)
    {
        d[i + 1] += d[i] / 10; d[i] %= 10;
        if (d[i] < 0) { d[i + 1]--; d[i] += 10; }
    }
    while (d.size() >= 2 && d.back() == 0) d.pop_back();
}

void operator += (const bignum &a) {
    const vi &c = a.d;
    d.resize(max(c.size(), d.size()));
    for (int i = 0; i < c.size(); ++i) d[i] += c[i];
    fix();
}

void operator -= (const bignum &a) { 
    const vi &c = a.d;
    d.resize(max(c.size(), d.size()));
    for (int i = 0; i < c.size(); ++i) d[i] -= c[i];
    fix();
}

void out()   {  for (int i = int(d.size()) - 1; i >= 0; --i) cout << d[i]; }
void outln() { out(); putchar('\n'); }

};

int main() { int n; cin >> n;

vector<bignum> f(n + 1);
f[0] = f[1] = bignum(1);
for (int i = 2; i <= n; ++i)
    for (int j = n; j >= i; --j)
        f[j] += f[j - i];

f[n] -= 1;
f[n].out();

}

My question

Can I solve the problem in $$$O(n^2)$$$ or in $$$O(n^2 \times polylog(n))$$$
Can I find the n_th element faster than $$$O(n^3)$$$

Rev.	By	When	Δ	Comment
en4	SPyofgame	2020-08-30 16:48:18	13
en3	SPyofgame	2020-08-30 16:18:25	7	Tiny change: 'roblem in Linear $O(n^2)$ ' -> 'roblem in $O(n^2)$ '
en2	SPyofgame	2020-08-30 12:55:06	64	Tiny change: 'he *n_th element ' -> 'he n_th element '
en1	SPyofgame	2020-08-30 12:52:29	5147	Initial revision (published)

About the problem

My approach for small n

My approach for bigger n

include

include

include

define all(x) (x).begin(), (x).end()

My question

History