QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 256 MB Total points: 100
[+11]

# 7774. 基础寄术练习题

Statistics

对于长度为 n 的序列 a,定义 f(a)=1ni=ksi,其中 si{an} 的前缀和数组,k 是给定的常数且 1k2

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

  • a 的长度为 n
  • i,jaiaj
  • 1aim

求它们的 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

限制与约定

对于所有数据,保证 2nm100108<p<1.07×109p 为质数,1k2

  • Subtask 1 (10 pts):m20
  • Subtask 2 (25 pts):k=1
  • Subtask 3 (15 pts):n=m30
  • Subtask 4 (10 pts):m30
  • Subtask 5 (15 pts):m40
  • Subtask 6 (10 pts):m70
  • Subtask 7 (15 pts):m100

时间限制:2s

空间限制:512MB