PID550 / [IPSC2010]Lovely stamps
题目描述

题目背景

Peter 爱好集邮。最近他和他的妈妈 Lucia 一起去购物,当经过一家邮局时,Peter 开始缠他的老妈要零花钱买邮票。这个邮局一共出售 N 种一元邮票和 M 种二元邮票。

Peter 从妈妈那里拿到了 K 元钱,并且他想把所有的钱都花掉。注意他可能会买同一种邮票很多张,你可以假定邮局有足够的各种邮票。

现在,Peter 在思考他有多少种购买邮票的方法。

题目描述

给定整数 N、M、K 和质数 P。

你的任务是求出 Z 模 P,Z 表示 Peter 共有 Z 种方式把所有 K 元钱花完。

题目来源:IPSC 2010

翻译:wish

输入格式

输入文件的第一行包含一个整数 T 表示测试数据的组数。每组测试数据之前都有一个空行。

每组数据只有一行四个数 N、M、K 和 P。

数据规模:

3 <= P <= 1000000

对于小数据,0 <= N, M <= 1000

对于大数据,0 <= N, M <= 300,1 <= K <= 1000000000000 = 10^12

输出格式

对于每组测试数据输出一行一个整数:总计不同的方式数,模 P。

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论