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

HDU 3482-Good Serial Inc.[解题报告]HOJ

Good Serial Inc.

问题描述 :

Good Serial Inc. (GSI) produces integer sequences with length N, in which every element is an integer in range [1, M].
They call a sequence S is good if the sequence has the following property: for every substring of S with length M, i.e., S[i -> i+m-1], all the elements in the substring are the same or all the elements are distinct(different from each other).
The company GIS is designed to produce good sequences. But how many different good 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 ≤ 1000000, 1 ≤ M ≤ 1000000 ).
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 ≤ 1000000, 1 ≤ M ≤ 1000000 ).
The input ends up with two negative numbers, which should not be processed as a case.

样例输入:

4 4
3 5
-1 -1

样例输出:

28
125
#include<iostream>
using namespace std;
#define M 987654321
int n,m;

__int64 deal(int m,int n)
{
	int i,j;
	__int64 ans=1;

	if(m==1)
		return 1;
	if(n>=m)
	{
		if(m==2)
		{
			for(i=1;i<=n;i++)
				ans=ans*m%M;
		}
		else//return A(m,m)+m
		{
			for(i=1;i<=m;i++)
				ans=(ans*i)%M;
			ans+=m;
		}
		return ans;
	}
	else if(n<m)
	{
		for(i=1;i<=n;i++)
			ans=ans*m%M;
		return ans;
	}
}

int main()
{
	while(scanf("%d%d",&n,&m)!=EOF&&!(n==-1&&m==-1))
	{
		printf("%I64d/n",deal(m,n));
	}
}

参考:http://blog.csdn.net/abcjennifer/article/details/5800371