Number of partitions of n into at least two distinct parts

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

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 <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);
    }
    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)$$$

Comments (2)

Write comment?

navneet.h

4 years ago, # |

← Rev. 4 →

You could use the generating function given in oeis, and use divide and conquer multiplication on each individual polynomial, and while that restrict the highest power of each part upto N, because we don't require more than N.

At certain depth from bottom prefer manual multiplication of polynomial because powers are sparse,after that depth use fft to speed because after some depth there will be more powers to deal with , even if you use fft for all depths .

it will be no more N^2 log, and coefficient of X^N will be your answer.

EDIT :: here is simple explanation of the above logic, Also a N^2 dp approach, link

→ Reply

MonsieurV

Can you give me a link of this problem?

SPyofgame's blog

About the problem

My approach for small n

My approach for bigger n

My question