#1796. 基础寄术练习题

    ID: 1796 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1422来源:qoj.ac数据:公开样例动态规划前缀和

基础寄术练习题

基础寄术练习题

题目描述

标题: 基础寄术练习题 - Problem - QOJ.ac

#7774. 基础寄术练习题

Statistics

The problem was used in the following contests:

对于长度为 n 的序列 a,定义 f(a)=1∏i=knsi,其中 si 为 {an} 的前缀和数组,k 是给定的常数且 1≤k≤2。

考虑所有满足以下三个条件的序列 a:

  • a 的长度为 n。
  • ∀i,j,ai≠aj。
  • 1≤ai≤m。

求它们的 f(a) 之和,答案对 p 取模。保证 p 是一个质数。

输入格式

第一行三个整数 n,m,k,p,分别代表序列长度,序列元素的上界和模数。

输出格式

一行一个整数表示答案对 p 取模后的结果。

样例

输入样例 1
2 3 2 1000000007
输出样例 1
966666675
输入样例 2
3 5 2 998244353
输出样例 2
148276980
输入样例 3
6 10 2 1004535809
输出样例 3
622165218
输入样例 4
30 40 1 265371653
输出样例 4
179937201

限制与约定

对于所有数据,保证 2≤n≤m≤100,108<p<1.07×109 且 p 为质数,1≤k≤2。

  • Subtask 1 (10 pts):m≤20。
  • Subtask 2 (25 pts):k=1。
  • Subtask 3 (15 pts):n=m≤30。
  • Subtask 4 (10 pts):m≤30。
  • Subtask 5 (15 pts):m≤40。
  • Subtask 6 (10 pts):m≤70。
  • Subtask 7 (15 pts):m≤100。

时间限制:2s。

空间限制:512MB。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

2 3 2 1000000007
966666675

样例 2

3 5 2 998244353
148276980