Submission #1185609

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185609		Unforgettablepl	Star Trek (CEOI20_startrek)	C++20	23 / 100	1097 ms	45896 KiB

startrek

#include <bits/stdc++.h>
using namespace std;

#define int __int128 

const int modulo = 1e9+7;


int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N,D;
    {
        long long n,d;
        cin >> n >> d;
        N=n;
        D=d;
    }
    vector<vector<int>> adj(N+1);
    for(int i=1;i<N;i++){
        int a,b;
        {
            long long x,y;
            cin>>x>>y;
            a=x;
            b=y;
        }
        adj[a].emplace_back(b);
        adj[b].emplace_back(a);
    }
    vector DPbase(N+1,vector<int>(4));
    vector DPend(N+1,vector<int>(4));
    function<pair<int,int>(int,int)> dfs = [&](int x,int p){
        int children = 0;
        pair<int,int> ans;
        int sumzero = 0;
        int sumone = 1;
        int cntzero = 0;
        for(int&i:adj[x])if(i!=p){
            auto t = dfs(i,x);
            if(t.first){cntzero++;sumzero+=t.second;}
            else sumone+=t.second;
        }
        if(cntzero){
            ans.first = 0;
            if(cntzero==1)ans.second=sumzero;
            else ans.second = 0;
        } else {
            ans.first = 1;
            ans.second=sumone;
        }
        return ans;
    };
    for(int i=1;i<=N;i++){
        auto t = dfs(i,0);
        if(t.first==0){
            DPbase[i][2]=N-t.second;
            DPbase[i][0]=t.second;
            DPend[i][2]=1;
        } else {
            DPbase[i][3]=N-t.second;
            DPbase[i][1]=t.second;
            DPend[i][3]=1;
        }
    }
    DPbase[0][0]=1;
    DPend[0][0]=-1;
    auto binexpo = [&](int x,int p){
        if(p==-2)return x;
        int ans = 1;
        while(p){
            if(p&1){
                ans*=x;
                ans%=modulo;
            }
            p/=2;
            x*=x;
            x%=modulo;
        }
        return ans;
    };
    auto combine = [&](vector<vector<int>> &DP1,vector<vector<int>> &DP2){
        vector DP(N+1,vector<int>(4));
        vector<int> sums(4);
        for(int i=1;i<=N;i++){
            for(int j=0;j<4;j++){
                sums[j]+=DP2[i][j];
                sums[j]%=modulo;
            }
        }
        for(int i=0;i<4;i++)sums[i]%=modulo;
        for(int i=1;i<=N;i++){
            DP[i][0]=(DP1[i][1]*sums[1])%modulo+(DP2[i][0]*sums[0])%modulo;
            DP[i][0]%=modulo;
            DP[i][1]=(DP1[i][1]*sums[0])%modulo+(DP2[i][0]*sums[1])%modulo;
            DP[i][1]%=modulo;
            DP[i][2]=(DP1[i][2]*binexpo(N,2*(DP2[0][0])))%modulo+
                    (DP1[i][0]*sums[2])%modulo+
                    (DP1[i][1]*sums[3])%modulo;
            DP[i][2]%=modulo;
            DP[i][3]=(DP1[i][3]*binexpo(N,2*(DP2[0][0])))%modulo+
                    (DP1[i][1]*sums[2])%modulo+
                    (DP1[i][0]*sums[3])%modulo;
            DP[i][3]%=modulo;
        }
        DP[0][0]=(DP1[0][0]+DP2[0][0])%(modulo-1);
        return DP;
    };
    function<vector<vector<int>>(int)> solve = [&](int d){
        if(d==1)return DPbase;
        auto half = solve(d/2);
        auto DP = combine(half,half);
        if(d&1)DP=combine(DP,DPbase);
        return DP;
    };
    auto s = solve(D);
    cout << (long long)combine(s,DPend)[1][2] << '\n';
}

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