Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
long long dp[2][2][25];
long long ans[130][130][25];
int alen[130][130];
void sol(int n, int m) {
    memset(dp, 0, sizeof(dp));
    int i, j, k, roll = 1;
    int p, q;
    int dplen[2][2] = {};
    dp[1][0][0] = m-2; // none one tail
    dp[1][1][0] = 1; // one tail
    ans[m][1][0] = m-1;
#define base 100000000000LL
    for(i = 1; i < n;) {
        memset(dp[1-roll], 0, sizeof(dp[0]));
        memset(dplen[1-roll], 0, sizeof(dplen[0]));

        for(p = 0; p <= dplen[roll][0]; p++)
            dp[1-roll][1][p] = dp[roll][0][p];
        dplen[1-roll][1] = dplen[roll][0];
        for(p = 0; p <= dplen[roll][1]; p++)
            dp[1-roll][1][p] += dp[roll][1][p];
        dplen[1-roll][1] = max(dplen[1-roll][0], dplen[roll][1]);
        dplen[1-roll][1] += 5;
        for(p = 0; p <= dplen[1-roll][1]; p++) {
            if(dp[1-roll][1][p] >= base) {
                dp[1-roll][1][p+1] += dp[1-roll][1][p]/base;
                dp[1-roll][1][p] %= base;
            }
        }
        while(dplen[1-roll][1] > 0 && dp[1-roll][1][dplen[1-roll][1]] == 0)
            dplen[1-roll][1]--;

        for(p = 0; p <= dplen[roll][0]; p++)
            dp[1-roll][0][p] = dp[roll][0][p]*(m-1);
        dplen[1-roll][0] = dplen[roll][0];
        for(p = 0; p <= dplen[roll][1]; p++)
            dp[1-roll][0][p] += dp[roll][1][p]*(m-2);
        dplen[1-roll][0] = max(dplen[1-roll][0], dplen[roll][1]);
        dplen[1-roll][0] += 5;
        for(p = 0; p <= dplen[1-roll][0]; p++) {
            if(dp[1-roll][0][p] >= base) {
                dp[1-roll][0][p+1] += dp[1-roll][0][p]/base;
                dp[1-roll][0][p] %= base;
            }
        }
        while(dplen[1-roll][0] > 0 && dp[1-roll][0][dplen[1-roll][0]] == 0)
            dplen[1-roll][0]--;

        roll = 1-roll;
        i++;
        alen[m][i] = max(dplen[roll][0], dplen[roll][1]);
        for(q = 0; q <= alen[m][i]; q++)
            ans[m][i][q] = dp[roll][0][q]+dp[roll][1][q];
        alen[m][i] += 5;
        for(q = 0; q <= alen[m][i]; q++) {
            if(ans[m][i][q] >= base) {
                ans[m][i][q+1] += ans[m][i][q]/base;
                ans[m][i][q] %= base;
            }
        }
        while(alen[m][i] > 0 && ans[m][i][alen[m][i]] == 0)
            alen[m][i]--;
    }
}
int main() {
    int n, m, i;
    for(m = 4; m <= 128; m++)
        sol(100, m);
    while(scanf("%d %d", &m, &n) == 2) {
        if(m == 0)  break;
        printf("%lld", ans[m][n][alen[m][n]]);
        for(i = alen[m][n]-1; i >= 0; i--)
            printf("%011lld", ans[m][n][i]);
        puts("");
    }
    return 0;
}