Number of partitions of n into at least two distinct parts

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	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 <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