ICPC2019 선양사이버대회 K.Guanguan's Happy water(고스소원+역원+매트릭스 쾌속멱)

제목 링크

사고의 방향

코드

#include 
#define ll long long
using namespace std;
const ll maxn=80;
const ll mod=1e9+7;
typedef ll Mat[maxn][maxn];
ll p[maxn],f[maxn*2],sum[maxn*2],n,k;
Mat A;
void read(ll &x)
{
    ll f=1;x=0;char s=getchar();
    while(s'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
    x*=f;
}

//       
//   
void solve(){
    memset(A,0,sizeof(A));
    ll cur=k+1;
    //cout<>=1;
    }
    return ret;
}
ll inv(ll v,ll modd){
    return pow_mod(v%modd,modd-2,modd);
}

void gauss_elimin(){
    for(ll i=0;i=0;i--){
        for(ll j=i+1;j>=1;
    }
    return ans;
}
 
//     
ll work(){
	ll i,j;
	for(i=1;i<=len;i++)
        e.mt[i][i]=1;
    memset(a.mt,0,sizeof(a.mt));
    for(i=1;i<=len;i++){
    	if(i==1){
    		a.mt[1][1]=1; 
    		for(j=2;j<=len;j++){
    			a.mt[1][j]=p[j-2];
    		}
    		continue;
    	}
    	if(i==2){
    		for(j=2;j<=len;j++){
    			a.mt[2][j]=p[j-2];
    		}
    		continue;
    	}
    	a.mt[i][j-1]=1;
    }
    matt al=pow(a,n-2*k);
    ll xx[maxn],x[maxn],ans=0;
    for(i=1;i<=k;i++)xx[i]=f[k+i];xx[k+1]=sum[2*k];
    for(i=1;i<=len;i++)x[len-i+1]=xx[i];
	for(i=1;i<=len;i++){
		ans+=al.mt[1][i]*x[i];
		ans%=mod;
	}
    return ans;
}


int main(){
    ll cas;
    read(cas);
    while(cas--){
        read(k);read(n);len=k+1;
		for(ll i=1;i<=2*k;i++)read(f[i]);
		memset(sum,0,sizeof(sum));
		for(ll i=1;i<=2*k;i++){
			sum[i]=sum[i-1]+f[i];
			sum[i]%=mod;
		}
		if(n<=2*k){
			cout<