求一分治算法的问题的解法

rockerz

输入为N和C。你要把N个连续自然数任意排列。如果i在j前面，并且i>j,积分+1。问题要求积分必须等于C。输出有多少种排列方法。 0<=N<=1000  0<=C<=10,000

示例：　１４３２ 积分为3， 因为 (４，３)，（４，２），（３，２）。

示例输入1
10 1
示例输出1
9

示例输入2
4 3
示例输出2
6

我已经写了一个暴力的算法，但是暴力终究不是解决问题的办法。。N超过50时就有64位数不同的排列方法了。。然后再一一查看是否符合C，电脑肯定卡爆。
声明：这道题不是作业，不是考试题。是我出于爱好去尝试的。本人已经自己网上找过，但无法找到解题思路。

附上我的暴力解法。

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int main()
{
        int a[50];
        int n,c,count=0,solc=0;;
        scanf("%d %d",&n,&c);
        for (int i=0;i<n;i++){
                a[i]=i;
        }
        do {
                count=0;
                for (int i=0;i<n;i++){
                        for (int j=i;j<n;j++){
                                if (a[i]>a[j])count++;
                        }
                        if (count>c)break;
                }
                if (count==c)solc++;
        } while (next_permutation(a,a+n));
        
        printf("%d",solc);
        return 0;
}

rockerz

自己顶一下