제출 #302366

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
302366		errorgorn	Star Trek (CEOI20_startrek)	C++14	50 / 100	1070 ms	82064 KiB

startrek

//雪花飄飄北風嘯嘯
//天地一片蒼茫

#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++){
      |                          ~^~~~~~~~~

• Subtask 1: 0 / 0
• Subtask 2: 7 / 7
• Subtask 3: 8 / 8
• Subtask 4: 15 / 15
• Subtask 5: 0 / 15
• Subtask 6: 20 / 20
• Subtask 7: 0 / 20
• Subtask 8: 0 / 15