pypy3 解法, 执行用时: 1867ms, 内存消耗: 31288K, 提交时间: 2021-08-20 23:34:41

M = 1000000007
def mul(a,b):
    ret = [[0 for i in range(len(b[0]))] for i in range(len(a))]
    for i in range(len(a)):
        for k in range(len(a[0])):
            for j in range(len(b[0])):
                ret[i][j] += a[i][k]*b[k][j]
                ret[i][j] %= M
    return ret
def getL(n):
    return [[int(i>=j) for j in range(n)] for i in range(n)]
def getU(n):
    return [[int(i<=j) for j in range(n)] for i in range(n)]

def pr(x):
    print('[')
    for l in x:
        print(l,',')
    print(']')
def powM(x, t):
    ret = [[int(i==j) for j in range(len(x))] for i in range(len(x))]
    while t:
        if(t%2 == 1): ret = mul(ret, x);
        t>>=1
        x = mul(x,x)
    return ret
def sum_(x):
    ret = 0
    for v in x:
        ret += sum(v)
        ret %= M
    return ret
gt =lambda: list(map(int, input().split()))
t ,= gt()
while t:
    t -= 1
    n,x,m = gt()
    ar = gt()
    ar.sort()
    rnd = m//x
    tmp = mul(getL(n),getU(n))
    ansM = mul([ar], powM(tmp,rnd//2))
    if(rnd%2 == 1):
        ansM = mul(ansM, getL(n))
    print(sum_(ansM))

C++ 解法, 执行用时: 739ms, 内存消耗: 488K, 提交时间: 2021-10-20 16:42:49

#include <bits/stdc++.h>
using namespace std;
const int N=55,p=1e9+7;
int t,n,x,m;
int a[N][N],b[N][N],res[N][N];
void mul(int c[][N],int a[][N],int b[][N]){
	int t[N][N];memset(t,0,sizeof t);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			for(int k=1;k<=n;k++){
				t[i][j]=1ll*(t[i][j]+1ll*a[i][k]*b[k][j]%p)%p;
			}
		}
	}
	memcpy(c,t,sizeof t);
}
signed main()
{
	cin>>t;
	while(t--){
		memset(a,0,sizeof a);
		memset(b,0,sizeof b);
		memset(res,0,sizeof res);
		cin>>n>>x>>m;
		x=m/x+1;
		for(int i=1;i<=n;i++) cin>>a[1][i];
        sort(a[1]+1,a[1]+1+n);
		for(int i=1;i<=n;i++){
			for(int j=n;j>n-i;j--){
				b[i][j]=1;
			}
		}
		while(x){
			if(x&1) mul(a,a,b);
			mul(b,b,b);
			x>>=1;
		}
		cout<<a[1][n]<<'\n';
	}
}