首页 > ACM题库 > HDU-杭电 > HDU 3014-Counting Problem[解题报告]HOJ
2014
02-27

HDU 3014-Counting Problem[解题报告]HOJ

Counting Problem

问题描述 :

Tetris

See the 2 X 2 board above. AekdyCoin gets a N X N chessboard recently. But he think the color of the chessman is too dull (Only White and Black!).So AekdyCoin buys different kind of chessmen with different color, say blue, pink, yellow …Now AekdyCoin buys K kind of chessmen with different color, and the number of each kind is exactly Ai.

Now AekdyCoin begins to play with these chessmen. He wants to put all the chessmen he bought on the board, and of course every grid could only contain one single chessman.The Figure 2 shows a valid situation ,in this figure, AekdyCoin bought two kind of chessmen and the number of each is one.

Tetris

As we know, AekdyCoin is very clever. So he think about this question:What is the number of ways he could put all chessmen he bought on the N X N board?

After a several seconds , AekdyCoin gets a perfect idea about how to solve this problem. What about you?

Two situation are regard the same in Figure 3, but the different in Figure 4.

Tetris

But the ways that you can get by flip or circumrotate is not regard as the same!

输入:

The input consists of several test cases, but no more than 20.

There are two integers N, M in the first line of each case indicate the size of the board and M. You should output the remainder of answer after divided by M. (1<=N <=5000, 1<=M<=2*10^9)

The next line contain only one integer K indicates the kind of the chessmen AekdyCoin bought. (1<=k<=100)

Then the next line has exactly K integer where the i-th integer Ai indicate the number of the i-th kind of chessmen AekdyCoin bought.(1<=Ai<=5000)

输出:

The input consists of several test cases, but no more than 20.

There are two integers N, M in the first line of each case indicate the size of the board and M. You should output the remainder of answer after divided by M. (1<=N <=5000, 1<=M<=2*10^9)

The next line contain only one integer K indicates the kind of the chessmen AekdyCoin bought. (1<=k<=100)

Then the next line has exactly K integer where the i-th integer Ai indicate the number of the i-th kind of chessmen AekdyCoin bought.(1<=Ai<=5000)

样例输入:

2 100
1
1
2 100
1
2

样例输出:

4
6

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3014

   思路:首先你必须推出这个公式(答案的解):A(n*n,s)/(A1!*A2!*……*Ak!)%m,这题的难点有如下几个:

   1、模运算中有除法,并且不能保证分子与m互素,呵呵,还好以前遇到过这种情况,知道如何处理。

 2、如何设计快速的计算方法。

  对于第一个,可参见:http://hi.baidu.com/codeblood/blog/item/615c4e4a2482a4126a63e538.html,处理过程一样。

 对于第二问:主要对于分母计算的优化,由于计算Ai!中多有重复,于是避免这些重复就是了。

感受:有了正确的思路,还得有信心和耐心,tle了三次,以为是自己思路错误,看了别人的,没有,结果wa了,后来改了一下输入格式(%lld变为%I64d)就ac了.

参考:http://hi.baidu.com/codeblood/item/872779ffdd2c63f91a111f19


  1. 这道题目的核心一句话是:取还是不取。
    如果当前取,则index+1作为参数。如果当前不取,则任用index作为参数。

  2. 站长好。我是一个准备创业的互联网小白,我们打算做一个有关国*际*游*学的平台。手上也有了一些境外资源。现阶段的团队现在没有cto.原意出让一些管理股寻找一个靠谱的技术专家做合伙人, 不知道是不是能得到您的帮助。发个帖子或者其他方式。期待您的回应。可以加我微信tianxielemon聊聊。