Codeforces587B-Duff in Beach
传送门
题意：
给出一个有l个数的序列，序列每n个数一循环，在每个循环里取一个数，一共取1-k个数，要求取出来的子序列要递增，求方案数。n×k≤1e6 l≤1e18

Solution：
DP，f[i][j]表示取了i次，最后一项取的位置是j的方案数，我们能迅速的想到一个转移方程：

f[i][j]=∑k=0,ak≤ajn−1f[i−1][k] f [ i ] [ j ] = ∑ k = 0 , a k ≤ a j n − 1 f [ i − 1 ] [ k ]

发现暴力转移会T，考虑优化：
然后就写了2小时树状数组最后发现我写的方式无法查询TAT
经过机房神犇点拨（orz ckw），发现了每个新状态的转移是不受i的限制的，所以说我们可以把整个数组排序后用前缀和来优化转移。我们可以记录一个sum[i]表示转移到第i层后的答案和，设f[i]表示所选的最后一项的位置是i的方案数，那么 f[i]=sum[in−1] f [ i ] = s u m [ i n − 1 ] ，最后统计答案时，对于每个f[i],它对答案的贡献为 ((l−i−1n+1)∗f[i] ( ( l − i − 1 n + 1 ) ∗ f [ i ] （下标从0开始所以要-1），至于为什么相信大家仔细思考一下就可以知道了。

代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int n,k;
long long l;
int mod=1000000007;
long long f[1000100];
int sum[1000010];
pair<int,int> p[1000100];
int a[1000100],cnt;
int ans=0;
void plu(int &a,int b)
{
    a=(1ll*a+b)%mod;
}
int main()
{

    scanf("%d%lld%d",&n,&l,&k);
    for (int i=0;i<n;i++)
        scanf("%d",&a[i]);
    for (int i=0;i<n*k;i++)
        p[i]=make_pair(a[i%n],i);
    sort(p,p+n*k);
    for (int i=0;i<n*k;i++)
    {
        if (p[i].second<n) f[p[i].second]=1;
        else f[p[i].second]=sum[p[i].second/n-1];
        plu(sum[p[i].second/n],f[p[i].second]);
        if (p[i].second<l)
        {
            plu(ans,(1ll*f[p[i].second]*(((l-p[i].second-1)/n)%mod+1))%mod);
        }
    }
    printf("%d",ans);
}

PS：终于会在markdown上写数学公式了QWQ