Submission #1306808

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306808		cpismylifeOwO	Star Trek (CEOI20_startrek)	C++20	50 / 100	1097 ms	47648 KiB

startrek

#include <bits/stdc++.h>

using namespace std;

const long long mod = 1e9 + 7;
const int MaxN = 1e6 + 5;

int n;
long long d;
vector<int> graph[MaxN];

void Inp()
{
    cin >> n >> d;
    for (int x = 1; x < n; x++)
    {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
}

struct Matrix
{
    vector<vector<long long>> mat;

    Matrix() = default;

    Matrix(vector<vector<long long>> _mat)
    {
        mat = _mat;
    }

    Matrix& operator = (const Matrix& other)
    {
        this->mat = other.mat;
        return *this;
    }

    Matrix operator + (const Matrix& other) const
    {
        Matrix res;
        assert((int)this->mat.size() == (int)other.mat.size());
        res.mat.resize((int)this->mat.size());
        for (int x = 0; x < (int)this->mat.size(); x++)
        {
            assert((int)this->mat[x].size() == (int)other.mat[x].size());
            res.mat[x].resize((int)other.mat[x].size());
            for (int y = 0; y < (int)other.mat[x].size(); y++)
            {
                res.mat[x][y] = (this->mat[x][y] + other.mat[x][y]) % mod;
            }
        }
        return res;
    }

    Matrix operator - (const Matrix& other) const
    {
        Matrix res;
        assert((int)this->mat.size() == (int)other.mat.size());
        res.mat.resize((int)this->mat.size());
        for (int x = 0; x < (int)this->mat.size(); x++)
        {
            assert((int)this->mat[x].size() == (int)other.mat[x].size());
            res.mat[x].resize((int)other.mat[x].size());
            for (int y = 0; y < (int)other.mat[x].size(); y++)
            {
                res.mat[x][y] = (this->mat[x][y] - other.mat[x][y]) % mod;
            }
        }
        return res;
    }

    Matrix operator * (const Matrix& other) const
    {
        Matrix res;
        assert((int)this->mat[0].size() == (int)other.mat.size());
        res.mat.resize((int)this->mat.size());
        for (int x = 0; x < (int)res.mat.size(); x++)
        {
            res.mat[x].resize((int)other.mat[x].size());
            for (int y = 0; y < (int)res.mat[x].size(); y++)
            {
                res.mat[x][y] = 0;
                for (int z = 0; z < (int)this->mat[0].size(); z++)
                {
                    res.mat[x][y] = (res.mat[x][y] + this->mat[x][z] * other.mat[z][y] % mod) % mod;
                }
            }
        }
        return res;
    }

    void Print()
    {
        for (int x = 0; x < (int)mat.size(); x++)
        {
            for (int y = 0; y < (int)mat[x].size(); y++)
            {
                cout << mat[x][y] << " ";
            }
            cout << "\n";
        }
        cout << "\n";
    }
};

Matrix F[MaxN];
bool isW[MaxN];
int cntnow[MaxN];

void DFS(int u, int p)
{
    isW[u] = false;
    int cnt = 0;
    for (int v : graph[u])
    {
        if (v != p)
        {
            DFS(v, u);
            isW[u] |= !isW[v];
            cnt += !isW[v];
        }
    }
    cntnow[u] = cnt;
    F[u] = Matrix({{isW[u], 1}, {!isW[u], 0}});
    for (int v : graph[u])
    {
        if (v != p)
        {
            if (cnt == !isW[v])
            {
                F[u] = (F[u] + (Matrix({{0, 1}, {1, 0}}) * F[v]));
            }
            else
            {
                F[u] = (F[u] + (Matrix({{1, 1}, {0, 0}}) * F[v]));
            }
        }
    }
}

bool Wroot[MaxN];
Matrix PreRoot[MaxN];

void Exc()
{
    for (int x = 1; x <= n; x++)
    {
        DFS(x, -1);
        Wroot[x] = isW[x];
        PreRoot[x] = F[x];
    }
    Matrix change({{0, 0}, {0, 0}});
    Matrix sam({{0}, {0}});
    for (int x = 1; x <= n; x++)
    {
        sam.mat[!Wroot[x]][0]++;
        change = (change + PreRoot[x]);
    }
    if (d > 1)
    {
        d -= 2;
        sam = change * sam;
        while (d)
        {
            if (d & 1)
            {
                sam = change * sam;
            }
            change = change * change;
            d >>= 1;
        }
    }
    DFS(1, -1);
    long long res = (F[1].mat[0][0] * sam.mat[0][0] % mod + F[1].mat[0][1] * sam.mat[1][0] % mod) % mod;
    cout << (res % mod + mod) % mod;
}

int main()
{
    //freopen("C.INP", "r", stdin);
    //freopen("C.ANS", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int test = 1;
    //cin >> test;
    for (int x = 1; x <= test; x++)
    {
        Inp();
        Exc();
    }
    return 0;
}

• 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