题目链接
比赛感觉这个题感觉难到炸裂,不知道为啥过这么多,明明b题更简单的说。。赛后知道数据水暴力可以过。woc?我们正解a出来的感觉好亏啊。。不然b就有时间了。
题解:先高斯消元求出q,然后跑矩阵快速幂就行了。注意的是:高斯消元的所有除,改成乘逆元就行了。。
下面是ac代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
typedef ll Matrix[100][100];
const int N=150;
const int M=1e9+7;
int T,k;
ll n,a[N];
ll _ans;
Matrix A;
struct matrix{
ll m[75][75];
}ans, res;
ll ksm(ll base,int k){
ll res=1;
while(k){
if(k&1) res=(res*base)%M;
base=(base*base)%M;
k>>=1;
}
return res;
}
void gauss(Matrix A,int n)
{
int i,j,k,r;
for(int i=0; i<n; i++)
{
r=i;
for( j=i+1; j<n; j++)
if(fabs(A[j][i])>fabs(A[r][i]))r=j;
if(r!=i)
for(j=0; j<=n; j++)swap(A[r][j],A[i][j]);
for(k=i+1; k<n; k++)
{
ll f=A[k][i]*ksm(A[i][i], M-2) % M;
for(j=i; j<=n; j++)
A[k][j]=(A[k][j]-f*A[i][j])%M;
}
}
for(i=n-1; i>=0; i--)
{
for(j=i+1; j<n; j++)
A[i][n]=(A[i][n]-A[j][n]*A[i][j])%M;
// A[i][n]/=A[i][i];
A[i][n]=(A[i][n]*ksm(A[i][i],M-2))%M;
}
}
ll sum = 0;
void init()
{
memset(ans.m, 0, sizeof(ans.m));
for (int i = 0; i < k; i++)
{
ans.m[0][i] = a[k-i-1];
}
ans.m[0][k] = sum;
memset(res.m, 0, sizeof(res.m));
for (int i = 0; i < k; i++)
{
res.m[i][0] = A[k-i-1][k];
}
for (int i = 1; i <k; i++)
{
res.m[i-1][i] = 1;
}
res.m[0][k] = res.m[k][k] = 1;
// for (int i = 0; i <= k; i++)
// {
// for (int j = 0; j <= k; j++)
// {
// cout << res.m[i][j] << " ";
// }
// cout << endl;
// }
}
matrix mul(matrix a, matrix b)
{
matrix c;
for (int i = 0; i <= k; i++)
{
for (int j = 0; j <= k; j++)
{
c.m[i][j] = 0;
for (int g = 0; g <= k; g++)
{
c.m[i][j] = (c.m[i][j] + a.m[i][g]*b.m[g][j]%M)%M;
}
}
}
return c;
}
void _pow(ll n)
{
while(n)
{
if (n&1) ans = mul(ans, res);
n >>=1;
res = mul(res, res);
}
}
int main(){
scanf("%d",&T);
while(T--){
_ans = 0;
sum = 0;
scanf("%d%lld",&k,&n);
for(int i=0;i<2*k;i++)
scanf("%lld",&a[i]);
if(n<=2*k){
for(int i=0;i<n;i++)
_ans=(_ans+a[i])%M;
printf("%lld\n",_ans);
continue;
}
for(int i=k;i<2*k;i++){
A[i-k][k]=a[i];
for(int j=i-k;j<i;j++)
A[i-k][j-i+k]=a[j];
}
gauss(A,k);
sum = 0;
for (int i = 0; i < k-1; i++)
sum = (sum + a[i]) % M;
// for (int i = 0; i < k; i++)
// cout << A[i][k] << endl;
init();
_pow(n-k+1);
printf("%lld\n", ans.m[0][k]%M);
}
return 0;
}