题目链接

题目思路

这个题目的关键点在于那一瞬间该如何去吃贪吃蛇

按大小排序得\(l_1<l_2<l_3...<l_n\)

那么最优的吃法是\(l_{n-1}\)吃\(l_{n}\)，然后\(l_{n-2}\)吃\(l_{n-1}\)一直到\(l_1\)吃\(l_2\)

然后第二轮再这样按照权值排序吃即可

为什么是这样 感觉比较显然 也不知道如何证明

但是暴力肯定是不行的可以构造一个下三角全1矩阵然后矩阵快速幂即可

$ \begin{bmatrix} l_1 & l_2&l_3&...&l_n \end{bmatrix}$ \(\begin{bmatrix} 0&0&0&...&&1\\0&0&0&...&1&1\\ 0&0&0&...1&1&1 \\&&&&&\\1&1&1&1&1&1 \end{bmatrix}=\) \(\begin{bmatrix} p_1 & p_2&p_3&...&p_n \end{bmatrix}\)

并且\(p\)也是单调上升的 则可以矩阵快速幂

代码

#include<bits/stdc++.h>
#define fi first
#define se second
#define debug printf(" I am here\n");
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pii;
mt19937 rnd(time(0));
const ll INF=0x3f3f3f3f3f3f3f3f;
const int maxn=50+5,inf=0x3f3f3f3f,mod=1e9+7;
const double eps=1e-10;
int n,x,m;
int a[maxn];
struct matrix{
    ll a[maxn][maxn];
}base,ans;
matrix mul(matrix a,matrix b){
    matrix temp;
    memset(temp.a,0,sizeof(temp.a)); //一定1要清空
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int k=1;k<=n;k++){
                temp.a[i][k]+=(a.a[i][j])*(b.a[j][k]);
                temp.a[i][k]%=mod;
            }
        }
    }
    return temp;
}
void qpow(ll n,ll b){
    while(b){
        if(b&1){
            ans=mul(ans,base);
        }
        base=mul(base,base);
        b=b>>1;
    }
}
signed main(){
    int _;scanf("%d",&_);
    while(_--){
        scanf("%d%d%d",&n,&x,&m);
        int b=m/x+1;
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        sort(a+1,a+1+n);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(i==j){
                    ans.a[i][j]=1;
                }else{
                    ans.a[i][j]=0;
                }
                if(n-i+1<=j){
                    base.a[i][j]=1;
                }else{
                    base.a[i][j]=0;
                }
            }
        }
        qpow(n,b);
        ll pr=0;
        for(int i=1;i<=n;i++){
            pr=(pr+1ll*ans.a[i][n]*a[i])%mod;
        }
        printf("%lld\n",pr);
    }

    return 0;
}