Preparing NOJ

分配座位问题

1000ms 65536K

Description:

南邮SCDA协会有了新家,会长要给会员分配座位,请你帮忙解决他的问题!

SCDA新家位置分配的原则是:(1)保证每一个会员周围紧邻的四个位置(前、后、左、右)都是空的,(2)每过一个星期,位置会重新分配;(3)所有分配方案各不相同。如果两个方案中,至少一个座位在一个方案被占,而在另一个方案中空着,我们认为这两个方案是不相同的。

为使问题简化,假设南邮SCDA协会有N个会员,新家所有座位构成一个M×K的网格(共有K排,每排M个座位,忽略过道)。

会长的问题是:给定NMK,共有多少个座位分配方案(结果对50000取模)。


Input:

输入包括多个测试用例,首先给出测试用例数C,接着给出C个测试用例。每一个测试用例包括一行,依次给出NMK1C10 1M8 1K1001N800


Output:

输出包括多行,对于每个测试用例输出一行,给出座位分配方案,结果对50000取模。


Sample Input:

2
1 2 3
2 5 1

Sample Output:

6
6

Note:

本题由旧版NOJ导入,来源:NUPT ACM

Info

NOJ

Provider NOJ

Code NOJ1193

Tags

Submitted 0

Passed 0

AC Rate 0%

Date 04/20/2019 10:03:10

Related

Nothing Yet