제출 #302366

#제출 시각아이디문제언어결과실행 시간메모리
302366errorgornStar Trek (CEOI20_startrek)C++14
50 / 100
1070 ms82064 KiB
//雪花飄飄北風嘯嘯 //天地一片蒼茫 #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <ext/rope> using namespace std; using namespace __gnu_pbds; using namespace __gnu_cxx; #define ll long long #define ii pair<ll,ll> #define iii pair<ii,ll> #define fi first #define se second #define endl '\n' #define debug(x) cout << #x << " is " << x << endl #define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--)) #define all(x) (x).begin(),(x).end() #define sz(x) (int)(x).size() #define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> //change less to less_equal for non distinct pbds, but erase will bug mt19937 rng(chrono::system_clock::now().time_since_epoch().count()); struct custom_hash { typedef unsigned long long ull; const ull FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); static ull splitmix64(ull x) { // http://xorshift.di.unimi.it/splitmix64.c x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } size_t operator()(ll x) const { return splitmix64(x + FIXED_RANDOM); } size_t operator()(const pair<int,int> &i)const{ return splitmix64((((ll)i.first)^(((ll)i.second)<<32))+FIXED_RANDOM); } }; const int MOD=1000000007; vector<vector<ll> > mul(vector<vector<ll> > i, vector<vector<ll> > j,int m){ vector<vector<ll> > res; for (int x=0;x<i.size();x++){ res.push_back(vector<ll>()); for (int y=0;y<i.size();y++){ res[x].push_back(0); for (int z=0;z<i.size();z++){ res[x][y]=(res[x][y]+i[x][z]*j[z][y])%m; } } } return res; } vector<vector<ll> > mexp(vector<vector<ll> > mat,long long p,int m){ if (p==1) return mat; vector<vector<ll> > res=mexp(mat,p>>1,m); res=mul(res,res,m); if (p&1) res=mul(res,mat,m); return res; } ll qexp(ll b,ll p,int m){ ll res=1; while (p){ if (p&1) res=res*b%m; b=b*b%m; p>>=1; } return res; } ll fix(ll i){ i%=MOD; if (i<0) i+=MOD; return i; } ll n,k; vector<int> al[100005]; struct pi{ ll a=0,b=0; }; pi add(pi i,pi j){ pi res; res.a=(i.a+j.a)%MOD; res.b=(i.b+j.b)%MOD; return res; } pi mul(pi i,pi j){ pi res; res.a=(i.a*j.b)%MOD; res.b=fix((i.a+i.b)*(j.a+j.b)-res.a); return res; } struct dat{ pi norm; pi extra; }; struct mat{ //operation of tree int v[4][4]; mat(int i){ memset(v,0,sizeof(v)); rep(x,0,4) v[x][x]=i; } mat(int a,int b,int c,int d){ memset(v,0,sizeof(v)); v[0][0]=b; v[1][0]=a; v[1][1]=(a+b)%MOD; v[2][2]=b; v[3][2]=a; v[3][3]=(a+b)%MOD; v[2][0]=d; v[3][0]=c; v[3][1]=(c+d)%MOD; } }; mat mul(mat &i, mat &j){ mat res=mat(0); rep(x,0,4) rep(y,0,4) rep(z,0,4) res.v[x][y]=(res.v[x][y]+i.v[x][z]*j.v[z][y])%MOD; return res; } pi pp; unordered_map<ii,dat,custom_hash> memo; int pa[100005]; vector<int> adj[100005]; vector<mat> fw[100005],bw[100005]; dat dfs(int i,int p){ if (memo.count(ii(i,p))) return memo[ii(i,p)]; mat matt=mat(1); if (pa[i]==0){ pa[i]=p; vector<mat> v; for (auto &it:al[i]){ if (it==p) continue; adj[i].push_back(it); auto res=dfs(it,i); v.push_back(mat(res.norm.a,res.norm.b,res.extra.a,res.extra.b)); } if (sz(v)==1) fw[i].push_back(v[0]),bw[i].push_back(v[0]); else if (sz(v)>1){ fw[i].push_back(v[0]); rep(x,1,sz(v)) fw[i].push_back(mul(fw[i].back(),v[x])); reverse(all(v)); bw[i].push_back(v[0]); rep(x,1,sz(v)) bw[i].push_back(mul(bw[i].back(),v[x])); reverse(all(bw[i])); } if (!v.empty()) matt=fw[i].back(); } else{ if (pa[i]!=-1){ auto res=dfs(pa[i],i); auto temp=mat(res.norm.a,res.norm.b,res.extra.a,res.extra.b); matt=mul(matt,temp); } if (!adj[i].empty()){ if (p==-1){ matt=mul(matt,fw[i].back()); } else{ int idx=distance(adj[i].begin(),lower_bound(all(adj[i]),p)); if (idx!=0) matt=mul(matt,fw[i][idx-1]); if (idx!=sz(adj[i])-1) matt=mul(matt,bw[i][idx+1]); } } } dat res; res.norm.a=matt.v[0][0],res.norm.b=matt.v[1][0]; res.extra.a=matt.v[2][0],res.extra.b=matt.v[3][0]; res.extra=add(res.extra,mul(res.norm,pp)); return memo[ii(i,p)]=res; } dat get(int i,int j){ pp.a=i,pp.b=j; memo.clear(); rep(x,0,100005){ pa[x]=0; adj[x].clear(); fw[x].clear(); bw[x].clear(); } dat temp; rep(x,1,n+1){ auto res=dfs(x,-1); temp.norm=add(temp.norm,res.norm); temp.extra=add(temp.extra,res.extra); } return temp; } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin.exceptions(ios::badbit | ios::failbit); memo.reserve(4096); memo.max_load_factor(0.25); cin>>n>>k; ll a,b; rep(x,1,n){ cin>>a>>b; al[a].push_back(b); al[b].push_back(a); } rep(x,1,n+1) sort(all(al[x])); vector<vector<ll> > mat={{0,0},{0,0}}; dat temp; temp=get(1,0); mat[0][0]=temp.extra.a%MOD,mat[1][0]=temp.extra.b%MOD; temp=get(0,1); mat[0][1]=temp.extra.a%MOD,mat[1][1]=temp.extra.b%MOD; //cout<<mat[0][0]<<" "<<mat[0][1]<<endl; //cout<<mat[1][0]<<" "<<mat[1][1]<<endl; if (k==1) mat={{1,0},{0,1}}; else mat=mexp(mat,k-1,MOD); temp=get(0,0); a=temp.norm.a%MOD,b=temp.norm.b%MOD; //cout<<a<<" "<<b<<endl; get((mat[0][0]*a+mat[0][1]*b)%MOD,(mat[1][0]*a+mat[1][1]*b)%MOD); cout<<dfs(1,-1).extra.b<<endl; }

컴파일 시 표준 에러 (stderr) 메시지

startrek.cpp: In function 'std::vector<std::vector<long long int> > mul(std::vector<std::vector<long long int> >, std::vector<std::vector<long long int> >, int)':
startrek.cpp:56:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for (int x=0;x<i.size();x++){
      |                  ~^~~~~~~~~
startrek.cpp:58:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         for (int y=0;y<i.size();y++){
      |                      ~^~~~~~~~~
startrek.cpp:60:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |             for (int z=0;z<i.size();z++){
      |                          ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...