首页 > ACM题库 > HDU-杭电 > HDU 3481-Bad Serial Inc.[解题报告]HOJ
2014
04-04

HDU 3481-Bad Serial Inc.[解题报告]HOJ

Bad Serial Inc.

问题描述 :

Bad Serial Inc. (BSI) produces integer sequences with length N, in which every element is an integer in range [1, M].
They call a sequence S is bad if all the M-substrings (substrings with length M) are bad.
They call an M-substring is bad if it’s not good. An M-substring is good if all the elements in the substring are the same or all the elements are distinct (different from each other).
The company BIS is designed to produce bad sequences. But how many different bad sequences are there? Since the answer will be very large, just output the result after module 987654321.

输入:

There are several cases. For each case, there is a line with two integers N, and M (1 ≤ N ≤ 100, 1 ≤ M ≤ 9).
The input ends up with two negative numbers, which should not be processed as a case.

输出:

There are several cases. For each case, there is a line with two integers N, and M (1 ≤ N ≤ 100, 1 ≤ M ≤ 9).
The input ends up with two negative numbers, which should not be processed as a case.

样例输入:

4 4
3 5
-1 -1

样例输出:

228
125

#include<cstdio>
#include<algorithm>

const int MOD = 987654321;

long long dp[110][10];

int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m),n>0)
    {
        if(m==1){puts("0");continue;}
        if(m==2){printf("%d\n",n==1?2:0);continue;}

        memset(dp,0,sizeof(dp));
        dp[1][1]=m;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<m;j++)
            {
                dp[i][j]%=MOD;

                dp[i+1][j+1]+=dp[i][j]*(m-j);//str[i+1]=new one
                for(int k=2;k<=j;k++)
                    dp[i+1][k]+=dp[i][j];//str[i+1]=str[i+1-k]

                if(j>1||i==1)
                {
                    for(int k=1;1+k<=m-1;k++)
                    {
                        dp[i+k][1]+=dp[i][j];
                    }
                }
            }
        }

        long long ans=0;
        for(int j=1;j<m;j++)
        {
            ans+=dp[n][j];
        }
        printf("%I64d\n",ans%MOD);
    }
    return 0;
}

参考:http://shaidaima.com/source/view/9642


  1. 老实说,这种方法就是穷举,复杂度是2^n,之所以能够AC是应为题目的测试数据有问题,要么数据量很小,要么能够得到k == t,否则即使n = 30,也要很久才能得出结果,本人亲测

  2. 博主您好,这是一个内容十分优秀的博客,而且界面也非常漂亮。但是为什么博客的响应速度这么慢,虽然博客的主机在国外,但是我开启VPN还是经常响应很久,再者打开某些页面经常会出现数据库连接出错的提示

  3. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。