题目描述

While Duff was resting in the beach, she accidentally found a strange array

b_{0},b_{1},…,b_{l-1}

consisting of

l

positive integers. This array was strange because it was extremely long, but there was another (maybe shorter) array,

a_{0},…,a_{n-1}

that

b

can be build from

a

with formula:

b_{i}=a_{i\ mod\ n}

where

a\ mod\ b

denoted the remainder of dividing

a

by

b

.

Duff is so curious, she wants to know the number of subsequences of

b

like

b_{i1},b_{i2},…,b_{ix}

( $ 0<=i_{1}&lt;i_{2}&lt;…&lt;i_{x}&lt;l $ ), such that:


  • 1<=x<=k

  • For each
    1<=j<=x-1

    ,

  • For each
    1<=j<=x-1

    ,

    b_{ij}<=b_{ij+1}

    . i.e this subsequence is non-decreasing.

Since this number can be very large, she want to know it modulo

10^{9}+7

.

Duff is not a programmer, and Malek is unavailable at the moment. So she asked for your help. Please tell her this number.

输入输出格式

输入格式:

The first line of input contains three integers,

n,l

and

k

(

1<=n,k

,

n×k<=10^{6}

and

1<=l<=10^{18}

).

The second line contains

n

space separated integers,

a_{0},a_{1},…,a_{n-1}

(

1<=a_{i}<=10^{9}

for each

0<=i<=n-1

).

输出格式:

Print the answer modulo

1000000007

in one line.

输入输出样例

输入样例#1: 复制
输出样例#1: 复制
输入样例#2: 复制
输出样例#2: 复制

说明

In the first sample case, . So all such sequences are: , , , , , , , , and .

dp 但是因为是在每个块内dp所以滕老师就选过来了?数据范围让我第一眼以为n^2过百万?

题意:相当于给b划分成若干块 然后每次只可以在这些块内选取 问有多少种方案使得构成不降序列 并且长度满足<=k

首先为了方便dp 离散化设dp[i][j]表示我选择了i个元素 当前选的是j

dp[i][j] = ∑dp[i-1][z] && z <= j

因为是小于等于均可 所以首先针对前面的答案进行累加 然后注意处理最后剩余块内的元素 加上我所有可以在后面零散的选取的方案数+(剩余块数*当前dp值)我当前这块其实和后面的块的效果都是一样的所以选谁都okay

 

分类: 动态规划数学

elijahqi

辣鸡蒟蒻一枚qwq 欢迎加qq qwq 2922945330