Submission #879582

#	Time	Username	Problem	Language	Result	Execution time	Memory
879582		Shayan86	Star Trek (CEOI20_startrek)	C++17	100 / 100	68 ms	18772 KiB

startrek

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

#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// Ofast, O0, O1, O2, O3, unroll-loops, fast-math, trapv

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

#define Mp          make_pair
#define sep         ' '
#define endl        '\n'
#define F	        first
#define S	        second
#define pb          push_back
#define all(x)      (x).begin(),(x).end()
#define kill(res)	cout << res << '\n', exit(0);
#define set_dec(x)	cout << fixed << setprecision(x);
#define fast_io     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io     freopen("input.txt", "r", stdin) ; freopen("output.txt", "w", stdout);

const ll MT = 2;
const ll N = 1e5 + 50;
const ll Mod = 1e9 + 7;

ll n, d;

struct shet{
    int col = 0, s0 = 0, s1 = 0, t0 = 0, cnt = 1;
};

ll calcute(shet a){
    if(a.t0 >= 2) return 0;
    if(a.t0 == 1) return a.s0;
    return a.s1 + 1;
}

shet add(shet a, shet b){
    if(b.col){
        a.s1 += b.cnt; a.cnt = calcute(a);
    }
    else{
        a.t0++; a.s0 += b.cnt; a.col |= 1; a.cnt = calcute(a);
    }
    return a;
}

shet del(shet a, shet b){
    if(b.col){
        a.s1 -= b.cnt; a.cnt = calcute(a);
    }
    else{
        a.t0--; a.s0 -= b.cnt; a.cnt = calcute(a);
        if(!a.t0) a.col = 0;
    }
    return a;
}

shet val[N], rval[N];

vector<int> adj[N];

ll mod(ll a, ll b = Mod){
    return (a%b+b)%b;
}

struct matrix{
    ll n, m, a[MT][MT];
    matrix(int n_, int m_, int x = 0){
        n = n_; m = m_;
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
                a[i][j] = x;
    }
    matrix operator * (const matrix &t){
        matrix r = matrix(n, t.m);
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
                for(int k = 0; k < t.m; k++)
                    r.a[i][k] = mod(r.a[i][k] + mod(a[i][j] * t.a[j][k]));
        return r;
    }
};

matrix Pow(matrix a, ll b){
    matrix ans = matrix(a.n, a.m);
    for(int i = 0; i < MT; i++) ans.a[i][i] = 1;

	for(; b; b /= 2, a = a * a){
        if(b % 2) ans = ans * a;
	}
	return ans;
}

ll power(ll a, ll b, ll md = Mod){
    ll ans = 1;
    for(; b; b /= 2, a = a * a % md){
        if(b % 2) ans = ans * a % md;
    }
    return ans;
}

void dfs(int v, int p = 0){
    for(int u: adj[v]){
        if(u == p) continue;
        dfs(u, v);
        val[v] = add(val[v], val[u]);
    }
}

void cal(int v, int p = 0){
    rval[v] = val[v];
    for(int u: adj[v]){
        if(u == p) continue;
        val[v] = del(val[v], val[u]);
        val[u] = add(val[u], val[v]);
        cal(u, v);
        val[u] = del(val[u], val[v]);
        val[v] = add(val[v], val[u]);
    }
}

int main(){
    fast_io;

    cin >> n >> d; d++;

    int u, v;
    for(int i = 1; i < n; i++){
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }

    dfs(1); cal(1);

    //for(int i = 1; i <= n; i++) cout << rval[i].col << sep << rval[i].cnt << sep << rval[i].t0 << endl;

    ll sum0 = 0, sum1 = 0, cnt0 = 0;
    for(int i = 1; i <= n; i++){
        if(rval[i].col) sum1 = mod(sum1 + rval[i].cnt);
        else sum0 = mod(sum0 + rval[i].cnt);
        if(!rval[i].col) cnt0++;
    }

    matrix m = matrix(2, 2);
    m.a[0][0] = mod(sum1 - sum0); m.a[0][1] = cnt0;
    m.a[1][0] = 0; m.a[1][1] = n*n%Mod;

    matrix ans = matrix(2, 1);
    ans.a[0][0] = 0; ans.a[1][0] = 1;

    ans = Pow(m, d-1) * ans;

    ll res = mod(rval[1].cnt * ans.a[0][0]);

    if(!rval[1].col) kill(res);
    res = mod(power(n*n%Mod, d-1) - res);
    kill(res);

}

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