POJ3187 Backward Digit Sums题解

CSDN同步

原题链接

考虑枚举所有情况：最多 (10 ! = 3.6 imes 10^6) 种情况。考虑用 (mathcal{O}(n)) 的时间计算出一个长度为 (n) 的序列按照此规则合并后的答案。这样不超过 (3.6 imes 10^7) 计算可以通过。

(n=2) 时：(ans = a_1 + a_2).

(n=3) 时：(ans = a_1 + 2a_2 + a_3).

(n=4) 时：(ans = a_1 + 3a_2 + 3a_3 + a_4).

很容易发现，这个系数其实就是杨辉三角的第 (n) 行。所以预处理一个杨辉三角就可以 (mathcal{O}(n)) 快速求解。

时间复杂度：(mathcal{O}(n! imes n)).

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

int n,k,a[11];
int f[11][11];

inline int check() {
        int sum=0;
        for(int i=1;i<=n;i++) sum+=a[i]*f[n][i];
        return sum==k;
}

int main(){
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++) a[i]=i;
        for(int i=1;i<=n;i++) f[i][1]=f[i][i]=1;
        for(int i=3;i<=n;i++) for(int j=2;j<i;j++) f[i][j]=f[i-1][j-1]+f[i-1][j];
        do {
                if(check()) {
                        for(int i=1;i<=n;i++) printf("%d ",a[i]);
                        return 0;
                }
        } while(next_permutation(a+1,a+1+n));
        return 0;
}