글 읽기 - 이게 왜 출력초과가 나는지 모르겠습니다....

ssipdukoreo 1년 전 0

벌래캠프에다가 mod가 들어가는 부분들을 다 지운 코듭니다

왜 계속 출력초과가 나는지 모르겠어요..

부탁드립니다!

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
long long int ans[1000000];

ll ipow(ll x,ll p){
   ll ret=1,piv=x;
   while(p){
      if(p&1) ret=ret*piv;
      piv=piv*piv;
      p>>=1;
   }
   return ret;
}

vector<ll> berlekamp_massey(vector<ll> x){
   vector<ll> ls,cur;
   ll lf,ld;
   for(int i=0;i<x.size();i++){
      ll t=0;
      for(int j=0;j<cur.size();j++) t=(t+1ll*x[i-j-1]*cur[j]);
      if((t-x[i])==0) continue;
      if(cur.empty()){
         cur.resize(i+1);
         lf=i;
         ld=(t-x[i]);
         continue;
      }
      ll k=-(x[i]-t)*ipow(ld,1);
      vector<ll> c(i-lf-1);
      c.push_back(k);
      for(int j=0;j<ls.size();j++) c.push_back(-ls[j]*k);
      if(c.size()<cur.size()) c.resize(cur.size());
      for(int j=0;j<cur.size();j++) c[j]=(c[j]+cur[j]);
      if(i-lf+(int)ls.size()>=(int)cur.size()){
         ls=cur;
         lf=i;
         ld=(t-x[i]);
      }
      cur=c;
   }
   for(int i=0;i<cur.size();i++) cur[i]=(cur[i]);
   return cur;
}

vector<ll> mul(vector<ll> rec,vector<ll> v,vector<ll> w){
   int m=v.size();
   vector<ll> t(2*m);
   for(int j=0;j<m;j++){
      for(int k=0; k<m; k++){
         t[j+k]+=1ll*v[j]*w[k];
      }
   }
   for(int j=2*m-1;j>=m;j--){
      for(int k=1;k<=m;k++){
         t[j-k]+=1ll*t[j]*rec[k-1];
      }
   }
   t.resize(m);
   return t;
}

ll get_nth(vector<ll> rec,vector<ll> dp,ll n){
   int m=rec.size();
   vector<ll> s(m),t(m);
   s[0]=1;
   if(m!=1) t[1]=1;
   else t[0]=rec[0];
   while(n){
      if(n&1) s=mul(rec,s,t);
      t=mul(rec,t,t);
      n>>=1;
   }
   ll ret=0;
   for(int i=0;i<m;i++) ret+=1ll*s[i]*dp[i];
   return ret;
}

ll guess_nth_term(vector<ll> x,ll n){
   if(n<x.size()) return x[n];
   vector<ll> v=berlekamp_massey(x);
   if(v.empty()) return 0;
   return get_nth(v,x,n);
}

int main(){
	long long n; 
    long long t;

    scanf("%lld", &t);
    for(int i=0;i<t;i++){
        long long int len;
        vector<long long int> temp = {0};
        scanf("%lld", &len);
        for(int j=0;j<len;j++){
            scanf("%lld", &n);
            temp.push_back(n);
        }
        ans[i]=guess_nth_term(temp, len+1);
    }
	for(int i=0;i<t;i++){
	    printf("%lld\n", ans[i]);
	}
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

이게 왜 출력초과가 나는지 모르겠습니다....

ssipdukoreo 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말