D. Duff in Beach

题意数字串a[0---n-1]，通过不断的重复组成了 b[0,---l-1]l<10^18,

让你计算出长度小于等于k的最长非递减子序列，满足，取得第 i 个取得是 L1 第i+1个取得是L2 ------ L1/n +1 = L2，通过这个我们先对原数组进行排序，排完后使用vector去计算dp[i][j]

及时第i个数放在第j位的方案总数，然后我们依次枚举放1 个 2 个3个。。。k，贡献分别是 l/n,l/n-1....1,这样再枚举那最后的余下的那一些。

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <vector>

#include <string.h>

using namespace std;

const int maxn=;

typedef long long LL;

const LL mod=;

int A[maxn],B[maxn],C[maxn],D[maxn],E[maxn];

vector<LL>G[maxn];

void init(int n,int k)

{

    for(int i=; i<=n; i++)

        {

             G[i].clear();

             for(int j=; j<=k; j++)G[i].push_back();

        }

}

int main()

{

    int n,k;LL l;

    while(scanf("%d%I64d%d",&n,&l,&k)==)

    {

        init(n,k);

        for(int i=;i<n; i++)

        {

            scanf("%d",&A[i]);

            B[i]=A[i];

        }

        sort(B,B+n);

        int ge=;

        C[]=;

        for(int i=; i<n;i++)

        {

            if(B[i]==B[ge-])C[ge-]++;

            else{

                B[ge++]=B[i]; C[ge-]=;

            }

        }

        LL num=l/n;

        LL ans=l%mod;

        LL uu=min(k*1LL,num+);

        int lest=l%n,numoflest=;

        sort(A,A+lest);

        if(lest>){

            E[]=;

            for(int i=; i<lest; i++)

            {

                if(A[i]==A[numoflest-])E[numoflest-]++;

                else{

                    A[numoflest++]=A[i]; E[numoflest-]=;

                }

            }

        }

        for(int i=; i<ge; i++)G[i][]=C[i];

        for(int i=; i<=k; i++)

            {

                 long long d=,S=;

                 int loc=;

                 for(int j=; j<ge; j++)

                 {

                     d+=G[j][i-];

                     d=d%mod;

                     G[j][i]=(d*C[j])%mod;

                     S=(S+G[j][i])%mod;

                     while(loc<lest&&A[loc]<B[j])loc++;

                     if(loc<lest && A[loc] == B[j])

                     {

                         if(i<=uu)

                            ans=(ans+(d*E[loc])%mod )%mod;

                     }

                 }

                 if( num - i +  >  )

                 {

                    long long  gg=( S * ( ( num - i +  )%mod ) )%mod;

                    ans=(ans+gg)%mod;

                 }

            }

        printf("%I64d\n",ans);

    }

    return ;

}

巴特西

D. Duff in Beach

最新文章

热门文章