[UVA][大、DP] 10722 - Super Lucky Numbers＠Morris' Blog｜PChome Online 人新台

Morris' Blog 我在摸索我存在的意、生命的意、涵及值。有真正神手般的害，套用模式是大部分的情。那害的我存在的意何，托出神的存在？有候不能怪人不我，我已始省思，什我有人的原因，而是全要靠人。有候我我不同，那是因我做不到很多人能到的事情。我不到、玩不起、得不明、理解得不多，我缺少的文能力，就是一切一切能的判定。此，我不得能做些人有助的事情。我知道我自己是不服的性格，但在我不得不。我有能力，因此我必。我到底世界作什？充不定性，而我是法出拔萃，想一般人似乎也回不了了。越大的挑需要越力的支持，而我的支持是什？最近人，但都是失的局，人能接受，不需要言，不需要通，一切所想都表不出。
49的鼓 6站台

2013-03-30 14:47:52| 人665| 回0 | 上一篇 | 下一篇

[UVA][大、DP] 1722 - Super Lucky Numbers

推 0 收藏 0 0 站台

Problem E	Super Lucky Numbers
Time Limit	2 Seconds

Some people believe that 13 is an unlucky number. So they always want to avoid the number 13. In some buildings you will find that there is no 13^th floor. After 12^th floor there is 14^th floor. In a number if there is no 13 (i.e. no ‘1’ is followed by a ‘3’) then we may call it a super lucky number. For example, 12345 is a super lucky number. But if any number contains 13 then it is not a super lucky number such as 13254 or 21345. Given the number of digits N in a number and a base B, you have to find out how many super lucky numbers are possible with N digits in the base B. B should be greater than 3, as because the digit 3 is present in only for base 4 or more. Note that leading 0’s are not significant. So, 011 is not a valid three digit number.

Input
There will be several lines in the input each containing two positive integers B and N, where 4 ≤ B ≤ 128 and N ≤ 100. A pair of zero will indicate the end of input and it should not be processed.

Output
For each line in the input print the count of super lucky numbers of N digits in the base B.

Sample Input	Output for Sample Input
4 2 5 3 0 0	11 91

Problem setter: Md. Bahlul Haider
Special thanks to Tanveer Ahsan

原本得 DP 推很，但速度很慢 dp[i][j] i 位 j 字尾。
那很 dp[i+1][j] = sigma(dp[i][k]) // j == 3 && k == 1 不合

那速度太慢了，修改成尾1 非1

dp[i+1][1] = dp[i][0] + dp[i][1]; //尾1
dp[i+1][0] = dp[i][0]*(m-1) + dp[i][1]*(m-2) //非1

#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;
}