题解 | #牛牛摆木棒#

class Solution {
public:
/**
*
* @param n int整型 木棒的个数
* @param k long长整型 第k个排列
* @return int整型vector
*/
vector<int> stick(int n, long long k) {
// write code here
long long dp[21][21][2];
long long acsum[21], dcsum[21];
dp[1][1][0] = 1;
dp[1][1][1] = 1;
for (int nn=2; nn<=n; nn++) {
acsum[0] = 0;
dcsum[nn] = 0;</int>

        for (int st=1; st<=nn-1; st++) {
            acsum[st]=acsum[st-1]+ dp[nn-1][st][1];

        }
        for (int st=nn-1; st>=0; st--) {
            dcsum[st]=dcsum[st+1]+ dp[nn-1][st][0];
        }

        for (int st=1; st<=nn; st++) {
            dp[nn][st][0] = acsum[st-1];
            dp[nn][st][1] = dcsum[st];

        }
    }
    set<int> S;
    for (int i=1; i<=n; i++) S.insert(i);
    vector<int> ans;
    int dir, p;
    for (int i=1; i<=n; i++) {
        if (dp[n][i][0]<k) k-= dp[n][i][0];
        else {ans.push_back(i); p=i; dir=0; S.erase(i); break;}
        if (dp[n][i][1]<k) k-= dp[n][i][1];
        else {ans.push_back(i); p=i; dir=1; S.erase(i); break;}

    }
    int startp;
    for (int i=n-1; i>=1; i--) {
        dir = 1-dir;
        if (dir==1) startp=1;
        else startp=p;
        for (int j=startp; j<=i; j++) {
            if (dp[i][j][dir]<k) k-=dp[i][j][dir];
            else {
                auto it=S.begin();
                for (int jj=1; jj<j; jj++) it++;
                ans.push_back(*it);
                S.erase(it);
                p=j; 
                break;
            }
        }
    }

    return ans;
}

};