oj.uz

답안 #974410

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
974410 2024-05-03T09:54:44 Z marvinthang Star Trek (CEOI20_startrek) C++17
38 / 100
 57 ms 16072 KB 
/*************************************
*    author: marvinthang             *
*    created: 03.05.2024 16:12:22    *
*************************************/

#include <bits/stdc++.h>

using namespace std;

#define                  fi  first
#define                  se  second
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define              ALL(v)  (v).begin(), (v).end()
#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define          REPD(i, n)  for (int i = (n); i-- > 0; )
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); --i >= _a; ) 
#define       FORE(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define      FORDE(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
    #include "debug.h"
#else
    #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
    #define DB(...) 23
    #define db(...) 23
    #define debug(...) 23
#endif

template <class U, class V> scan_op(pair <U, V>)  { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>)  { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")";  else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }

const int MOD = 1e9 + 7;
namespace MODULAR {
    inline void fasterLLDivMod(unsigned long long x, unsigned y, unsigned &out_d, unsigned &out_m) {
        unsigned xh = (unsigned)(x >> 32), xl = (unsigned)x, d, m;
    #ifdef __GNUC__
        asm(
            "divl %4 \n\t"
            : "=a" (d), "=d" (m)
            : "d" (xh), "a" (xl), "r" (y)
        );
    #else
        __asm {
            mov edx, dword ptr[xh];
            mov eax, dword ptr[xl];
            div dword ptr[y];
            mov dword ptr[d], eax;
            mov dword ptr[m], edx;
        };
    #endif
        out_d = d; out_m = m;
    }
    template <class T> T invGeneral(T a, T b) {
        a %= b;
        if (!a) return b == 1 ? 0 : -1;
        T x = invGeneral(b, a);
        return x == -1 ? -1 : ((1 - 1LL * b * x) / a + b) % b;
    }
    template <int MOD> struct ModInt {
        unsigned int val;
        ModInt(void): val(0) {}
        ModInt(const long long &x) { *this = x; }
        ModInt & normalize(const unsigned int &v) {
            val = v >= MOD ? v - MOD : v;
            return *this;
        }
        bool operator ! (void) { return !val; }
        ModInt & operator = (const ModInt &x) { val = x.val; return *this; }
        ModInt & operator = (const long long &x) { return normalize(x % MOD + MOD); }
        ModInt operator - (void) { return ModInt(MOD - val); }
        ModInt & operator += (const ModInt &other) { return normalize(val + other.val); }
        ModInt & operator -= (const ModInt &other) { return normalize(val + MOD - other.val); }
        ModInt & operator /= (const ModInt &other) { return *this *= other.inv(); }
        ModInt & operator *= (const ModInt &other) {
            unsigned dummy;
            fasterLLDivMod((unsigned long long) val * other.val, MOD, dummy, val);
            return *this;
        }
        ModInt operator + (const ModInt &other) const { return ModInt(*this) += other; }
        ModInt operator - (const ModInt &other) const { return ModInt(*this) -= other; }
        ModInt operator * (const ModInt &other) const { return ModInt(*this) *= other; }
        ModInt operator / (const ModInt &other) const { return ModInt(*this) /= other; }
        ModInt pow(long long n) const {
            assert(n >= 0);
            ModInt res = 1, a = *this;
            for (; n; n >>= 1, a *= a) if (n & 1) res *= a;
            return res;
        }
        ModInt inv(void) const {
            int i = invGeneral((int) val, MOD);
            assert(~i);
            return i;
        }
        ModInt & operator ++ (void) { return *this += 1; }
        ModInt & operator -- (void) { return *this -= 1; }
        ModInt operator ++ (int) { ModInt old = *this; operator ++(); return old; }
        ModInt operator -- (int) { ModInt old = *this; operator --(); return old; }
        friend ModInt operator + (const long long &x, const ModInt &y) { return ModInt(x) + y; }
        friend ModInt operator - (const long long &x, const ModInt &y) { return ModInt(x) - y; }
        friend ModInt operator * (const long long &x, const ModInt &y) { return ModInt(x) * y; }
        friend ModInt operator / (const long long &x, const ModInt &y) { return ModInt(x) / y; }
        friend ostream & operator << (ostream &out, const ModInt &x) { return out << x.val; }
        friend istream & operator >> (istream &in, ModInt &x) { long long a; in >> a; x = a; return in; }
        explicit operator bool(void) const { return val; }
        explicit operator int(void) const { return val; }
    };  
    using Modular = ModInt <MOD>;
}
using namespace MODULAR;

template <class T> struct Matrix {
    int numRow, numCol; vector <T> val;
    // accessors
    typename vector<T>::iterator operator [] (int r) { return val.begin() + r * numCol; }
    inline T & at(int r, int c) { return val[r * numCol + c]; }
    inline T get(int r, int c) const { return val[r * numCol + c]; }
    // constructors
    Matrix() {}
    Matrix(int r, int c): numRow(r), numCol(c), val(r * c) {}
    Matrix(const vector <vector <T>> &d) {
        numRow = d.size();
        numCol = numRow ? d[0].size() : 0;
        for (int i = 0; i < numRow; ++i) {
            assert((int) d[i].size() == numCol);
            copy(d[i].begin(), d[i].end(), back_inserter(val));
        }
    }
    Matrix & set_value(T v) {
        for (int i = 0; i < numRow * numCol; ++i) val[i] = v;
        return *this;
    }
    // convert to 2D vector
    vector <vector <T>> vecvec(void) const {
        vector <vector <T>> res(numRow);
        for (int i = 0; i < numRow; ++i)
            copy(val.begin() + i * numCol, val.begin() + (i + 1) * numCol, back_inserter(res[i]));
        return res;
    }
    operator vector <vector <T>> () const { return vecvec(); }
    static Matrix identity(int n) {
        Matrix res(n, n);
        for (int i = 0; i < n; ++i) res.at(i, i) = T(1);
        return res;
    }
    friend istream & operator >> (istream &in, Matrix &res) {
        for (T &x: res.val) in >> x;
        return in;
    }
    friend ostream & operator << (ostream &out, const Matrix &res) {
        for (int i = 0; i < res.numRow * res.numCol; ++i)
            cout << res.val[i] << " \n"[i % res.numCol == res.numCol - 1];
        return out;
    }
    Matrix operator - (void) {
        Matrix res(numRow, numCol);
        for (int i = 0; i < numRow * numCol; ++i) res.val[i] = -val[i];
        return res;
    }
    Matrix operator * (const T &v) {
        Matrix res = *this;
        for (T &x: res.val) x *= v;
        return res;
    } 
    Matrix operator / (const T &v) {
        Matrix res = *this;
        const T inv = T(1) / v;
        for (T &x: res.val) x *= inv;
        return res;
    }
    Matrix operator + (const Matrix &other) const {
        int M = numRow, N = numCol;
        assert(M == other.numRow); assert(N == other.numCol);
        Matrix res = *this;
        for (int i = 0; i < numRow * numCol; ++i) res.val[i] += other.val[i];
        return res;
    }
    Matrix operator - (const Matrix &other) const {
        int M = numRow, N = numCol;
        assert(M == other.numRow); assert(N == other.numCol);
        Matrix res = *this;
        for (int i = 0; i < numRow * numCol; ++i) res.val[i] -= other.val[i];
        return res;
    }
    Matrix operator * (const Matrix &other) const {
        int M = numRow, N = numCol, P = other.numCol;
        assert(N == other.numRow);
        Matrix t_other = other.transpose();
        Matrix res(M, P);
        for (int i = 0; i < M; ++i)
            for (int j = 0; j < P; ++j)
                res.at(i, j) = inner_product(this->val.begin() + N * i, this->val.begin() + N * (i + 1), t_other.val.begin() + t_other.numCol * j, T(0));
        return res;
    }
    Matrix & operator *= (const T &v) { return *this = *this * v; }
    Matrix & operator /= (const T &v) { return *this = *this / v; }
    Matrix & operator += (const Matrix &other) { return *this = *this + other; }
    Matrix & operator -= (const Matrix &other) { return *this = *this - other; }
    Matrix & operator *= (const Matrix &other) { return *this = *this * other; }
    Matrix pow(long long Exp) const {
        int M = numRow;
        assert(M == numCol); assert(Exp >= 0);
        Matrix res = identity(M);
        if (!Exp) return res;
        bool is_id = true;
        for (int i = 63 - __builtin_clzll(Exp); i >= 0; --i) {
            if (!is_id) res *= res;
            if (Exp >> i & 1) res *= *this, is_id = false;
        }
        return res;
    }
    Matrix transpose(void) const {
        Matrix res(numCol, numRow);
        for (int i = 0; i < numRow; ++i)
            for (int j = 0; j < numCol; ++j)
                res.at(j, i) = this->get(i, j);
        return res;
    }
};

// end of template

void process(void) {
	int n; long long d; cin >> n >> d;
	vector <vector <int>> adj(n);
	REP(i, n - 1) {
		int u, v; cin >> u >> v; --u; --v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	vector <int> cnt_lose(n), cnt_fw(n), cnt_fl(n), f(n);
	auto cal = [&] (int u) {
		if (cnt_lose[u] == 1) f[u] = cnt_fl[u];
		else if (!cnt_lose[u]) f[u] = cnt_fw[u] + 1;
		else f[u] = 0;
	};
	auto dfs = [&] (auto &&dfs, int u, int par) -> void{
		for (int v: adj[u]) if (v != par) {
			dfs(dfs, v, u);
			cnt_lose[u] += !cnt_lose[v];
			(cnt_lose[v] ? cnt_fw[u] : cnt_fl[u]) += f[v];
		}
		cal(u);
	};
	dfs(dfs, 0, 0);
	vector <int> g(n);
	vector <int> lst_win, lst_lose;
	auto dfs2 = [&] (auto &&dfs, int u, int par) -> void {
		(cnt_lose[u] ? lst_win : lst_lose).push_back(u);
		g[u] = f[u];
		for (int v: adj[u]) if (v != par) {
			cnt_lose[u] -= !cnt_lose[v];
			(cnt_lose[v] ? cnt_fw[u] : cnt_fl[u]) -= f[v];
			cal(u);
			cnt_lose[v] += !cnt_lose[u];
			(cnt_lose[u] ? cnt_fw[v] : cnt_fl[v]) += f[u];
			cal(v);
			dfs(dfs, v, u);
			cnt_lose[v] -= !cnt_lose[u];
			(cnt_lose[u] ? cnt_fw[v] : cnt_fl[v]) -= f[u];
			cal(v);
			cnt_lose[u] += !cnt_lose[v];
			(cnt_lose[v] ? cnt_fw[u] : cnt_fl[u]) += f[v];
			cal(u);
		}
	};
	dfs2(dfs2, 0, 0);
	Modular k;
	for (int u: lst_win) k += g[u];
	for (int u: lst_lose) k -= g[u];
	Matrix <Modular> base({{lst_lose.size(), 1LL * n * n}});
	Matrix <Modular> trans({
		{k, 0},
		{1, 1LL * n * n}
	});
	base *= trans.pow(d - 1);
	cout << (cnt_lose[0] ? base[0][1] - g[0] * base[0][0] : g[0] * base[0][0]) << '\n';
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); // cout.tie(nullptr);
	file("startrek");
	// int t; cin >> t; while (t--)
	process();
	// cerr << "Time elapsed: " << TIME << " s.\n";
	return (0^0);
}

Compilation message

startrek.cpp: In function 'void process()':
startrek.cpp:281:39: warning: narrowing conversion of 'lst_lose.std::vector<int>::size()' from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'long long int' [-Wnarrowing]
  281 |  Matrix <Modular> base({{lst_lose.size(), 1LL * n * n}});
      |                          ~~~~~~~~~~~~~^~
startrek.cpp: In function 'int main()':
startrek.cpp:30:61: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
startrek.cpp:292:2: note: in expansion of macro 'file'
  292 |  file("startrek");
      |  ^~~~
startrek.cpp:30:94: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
startrek.cpp:292:2: note: in expansion of macro 'file'
  292 |  file("startrek");
      |  ^~~~

Subtask #1
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 1 ms 344 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #4
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct

Subtask #5
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 39 ms 11728 KB Output is correct
13 Correct 57 ms 16072 KB Output is correct
14 Correct 31 ms 8664 KB Output is correct
15 Correct 35 ms 8608 KB Output is correct
16 Correct 36 ms 8396 KB Output is correct

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Incorrect 1 ms 348 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 39 ms 11728 KB Output is correct
13 Correct 57 ms 16072 KB Output is correct
14 Correct 31 ms 8664 KB Output is correct
15 Correct 35 ms 8608 KB Output is correct
16 Correct 36 ms 8396 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Incorrect 1 ms 348 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 1 ms 344 KB Output isn't correct
3 Halted 0 ms 0 KB -