Blog entries - Codeforces

#	User	Rating
1	Benq	3792
2	VivaciousAubergine	3647
3	Kevin114514	3603
4	jiangly	3583
5	strapple	3515
6	tourist	3470
7	dXqwq	3436
8	Radewoosh	3415
9	Otomachi_Una	3413
10	Um_nik	3376

#	User	Contrib.
1	Qingyu	158
2	adamant	152
3	Um_nik	146
4	Dominater069	144
5	errorgorn	141
6	cry	139
7	Proof_by_QED	137
8	YuukiS	135
9	chromate00	134
9	TheScrasse	134

Solution

Code

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

const int maxN = 1e6 + 5;

int a[maxN], pre[maxN];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n;
    cin >> n;

    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        pre[i] = max(pre[i - 1], a[i]);
    }

    int res = 0;
    for (int i = 1; i <= n; i++)
    {
        res = max(res, pre[i] - a[i]);
    }
    cout << res;
}

A2. Hiệu lớn nhất (Hard)

Solution

Code

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

const int maxN = 1e6 + 5;
const int INF = 1e9 + 7;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;

        int mx = -INF, mn = INF;
        for (int i = 1; i <= n; i++)
        {
            int a;
            cin >> a;
            mx = max(mx, a);
            mn = min(mn, a);
        }

        cout << mx - mn << "\n";
    }
}

B. Khoảng cách xa nhất

Solution

Code

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

const int maxN = 1e6 + 5;
const int INF = 1e9 + 7;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;
    while (t--)
    {
        int n, k;
        cin >> n >> k;

        map<int, int> first_index;
        first_index[0] = 0;

        int res = 0, tot = 0;
        for (int i = 1; i <= n; i++)
        {
            int x;
            cin >> x;
            tot += x;
            tot %= k;

            if (first_index.find(tot) == first_index.end())
            {
                first_index[tot] = i;
            }
            else
            {
                res = max(res, i - first_index[tot]);
            }
        }

        cout << res << "\n";
    }
}

C. Thu nhỏ mảng

Solution

Code

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

const int maxN = 1e6 + 5;
const int INF = 1e9 + 7;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;

        for (int i = 2; i <= n; i++)
            cout << i << " ";
        cout << 1 << "\n";
    }
}

D1. Thoát khỏi mê cung (Easy)

Solution

Code

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

const int maxN = 1e3 + 5;
const int MOD = 1e9 + 7;

int dp[maxN][maxN];

void prepare()
{
    dp[1][1] = 1;

    for (int i = 1; i < maxN; i++)
    {
        for (int j = 1; j < maxN; j++)
        {
            dp[i][j] += dp[i - 1][j] + dp[i][j - 1];
            dp[i][j] %= MOD;
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    prepare();

    int t;
    cin >> t;
    while (t--)
    {
        int n, m;
        cin >> n >> m;

        cout << dp[n][m] << "\n";
    }
}

D2. Thoát khỏi mê cung (Hard)

Solution

Code

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

const int maxN = 1e6 + 5;
const int MOD = 1e9 + 7;

#define int long long

int bPow(int n, int k, int mod = MOD)
{
    if (k == 0)
        return 1;

    int res = bPow(n, k >> 1, mod);
    res = res * res % mod;
    if (k & 1)
        res = res * n % mod;
    return res;
}

int fact[maxN], in_fact[maxN];

int C(int n, int k)
{
    if (k < 0 || k > n)
        return 0;

    return (fact[n] * in_fact[k] % MOD) * in_fact[n - k] % MOD;
}

void prepare()
{
    fact[0] = 1;
    for (int i = 1; i < maxN; i++)
    {
        fact[i] = (fact[i - 1] * i) % MOD;
    }

    in_fact[maxN - 1] = bPow(fact[maxN - 1], MOD - 2);
    for (int i = maxN - 2; i >= 0; i--)
    {
        in_fact[i] = (in_fact[i + 1] * (i + 1)) % MOD;
    }
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    prepare();

    int t;
    cin >> t;
    while (t--)
    {
        int n, m;
        cin >> n >> m;
        cout << C(n + m - 2, n - 1) << "\n";
    }
}

E. Số thứ K

Solution

Code

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

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;
    while (t--)
    {
        int n, k;
        cin >> n >> k;

        int need = (k - 1) / (n - 1);
        cout << k + need << "\n";
    }
}

F. Đếm cặp

Solution

Code

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

#define int long long

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;
    while (t--)
    {
        int n, x, y;
        cin >> n >> x >> y;

        vector<int> a(n);
        int tot = 0;

        for (int i = 0; i < n; i++)
        {
            cin >> a[i];
            tot += a[i];
        }
        sort(a.begin(), a.end());

        int mn = tot - y, mx = tot - x;

        int res = 0;
        for (int i = 0; i < n; i++)
        {
            int l = lower_bound(a.begin() + i + 1, a.end(), mn - a[i]) - a.begin();
            int r = upper_bound(a.begin() + i + 1, a.end(), mx - a[i]) - a.begin();

            res += (r - l);
        }

        cout << res << '\n';
    }
}

G1. Trò chơi trên cây (Easy)

Solution

Code

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

#define ll long long
#define fi first
#define se second
#define vi vector<int>
#define vl vector<ll>
#define vb vector<bool>
#define vs vector<string>
#define vc vector<char>
#define pii pair<int, int>
#define pib pair<int, bool>
#define pdd pair<double, double>
#define mii map<int, int>
#define mib map<int, bool>
#define mil map<int, ll>
#define mli map<ll, int>
#define si set<int>
#define vvi vector<vi>
#define vvl vector<vl>
#define vvb vector<vb>
#define vvc vector<vc>
#define vpi vector<pii>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sub(x, l, r) (x).begin() + l, (x).begin() + r
#define rsub(x, l, r) (x).rbegin() + l, (x).rbegin() + r
#define FOR(i, a, b) for (int i = a, _b = b; i <= _b; i++)
#define FORD(i, a, b) for (int i = a, _b = b; i >= _b; i--)

#define yes cout << "YES\n";
#define no cout << "NO\n";
#define yn yes else no
#define ny no else yes

// #define int ll

#ifdef VanLam
#include <debug.h>
#define cer(...) debug_out(__VA_ARGS__)
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define cer(...) 20
#define debug(...) 12
#endif

const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
const int maxN = 1e6 + 5;

int d;
vvi adj;
vi ind;
vb vis;

void dfs(int u)
{
    vis[u] = true;
    ind[u] = ++d;

    for (int v : adj[u])
    {
        if (!vis[v])
            dfs(v);
    }
}

void Van_Lam()
{
    int n, q;
    cin >> n >> q;
    adj.assign(n + 1, {});

    vi cnt(n + 1, 0);

    FOR(i, 0, n - 2)
    {
        int u, v;
        cin >> u >> v;

        adj[u].push_back(v);
        adj[v].push_back(u);

        cnt[u]++;
        cnt[v]++;
    }

    vis.assign(n + 1, false);
    ind.resize(n + 1);
    d = 0;
    FOR(i, 1, n)
    {
        if (cnt[i] == 1)
        {
            dfs(i);
            break;
        }
    }

    while (q--)
    {
        int u;
        cin >> u;
        if (!(ind[u] & 1) || (n - ind[u]) & 1) {
            cout << "Ron";
        } else {
            cout << "Hermione";
        }
    }
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    if (fopen("VanLam.inp", "r"))
    {
        freopen("VanLam.inp", "r", stdin);
        freopen("VanLam.out", "w", stdout);
    }

    int t = 1;
    // cin >> t;
    int testcase = 1;
    while (t--)
    {
        cer("- - - -", testcase++, "- - - -");
        Van_Lam();
        cout << '\n';
        cer("= = = = = = = = = =");
    }
    return 0;
}

G2. Trò chơi trên cây (Meium)

Solution

Code

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

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

#define ll long long
#define fi first
#define se second
#define vi vector<int>
#define vb vector<bool>
#define vc vector<char>
#define pii pair<int, int>
#define mii map<int, int>
#define mib map<int, bool>
#define vvi vector<vi>
#define vvb vector<vb>
#define vvc vector<vc>
#define vpi vector<pii>
#define vvpi vector<vpi>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sub(x, l, r) (x).begin() + l, (x).begin() + r
#define rsub(x, l, r) (x).rbegin() + l, (x).rbegin() + r
#define FOR(i, a, b) for (int i = a, _b = b; i <= _b; i++)
#define FORD(i, a, b) for (int i = a, _b = b; i >= _b; i--)

#define lcm(a, b) a / gcd(a, b) * b

#define Yes cout << "Yes\n";
#define No cout << "No\n";
#define YesNo Yes else No
#define NoYes No else Yes

template <class T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template <class T>
using max_heap = priority_queue<T, vector<T>, less<T>>;

#ifdef VanLam
#include <VanLam.h>
#define cer(...) debug_out(__VA_ARGS__)
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define __gcd(a, b) gcd(a, b)
#else
#define cer(...) 20
#define debug(...) 12
#define gcd(a, b) __gcd(a, b)
#endif

// #define int ll

const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
const int maxN = 1e6 + 5;

inline void prepare()
{
}

class Graph
{
public:
    int n;
    vvi adj;

    Graph(int n)
    {
        this->n = n;
        adj.assign(n + 1, vi());
    }

    void addEdge(int u, int v)
    {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    int dfs(int u, int par)
    {
        int res = 0;
        for (int v : adj[u])
        {
            if (v == par)
                continue;
            res |= (1 - dfs(v, u));
        }

        return res;
    }
};

inline void _VanLam_()
{
    int n, q;
    cin >> n >> q;

    Graph g(n);
    FOR(i, 1, n - 1)
    {
        int u, v;
        cin >> u >> v;
        g.addEdge(u, v);
    }

    int root;
    cin >> root;
    if (g.dfs(root, -1))
    {
        cout << "Ron\n";
    }
    else
    {
        cout << "Hermione\n";
    }
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    if (fopen("VanLam.inp", "r"))
    {
        freopen("VanLam.inp", "r", stdin);
        freopen("VanLam.out", "w", stdout);
    }

    prepare();

    int Case = 1;
    // cin >> Case;
    while (Case--)
    {
        cer("- - - -", Case, "- - - -");
        _VanLam_();
        cer("= = = = = = = = = =");
    }

    return 0;
}

G3. Trò chơi trên cây (Hard)

Solution

Code

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

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

#define ll long long
#define fi first
#define se second
#define vi vector<int>
#define vb vector<bool>
#define vc vector<char>
#define pii pair<int, int>
#define mii map<int, int>
#define mib map<int, bool>
#define vvi vector<vi>
#define vvb vector<vb>
#define vvc vector<vc>
#define vpi vector<pii>
#define vvpi vector<vpi>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sub(x, l, r) (x).begin() + l, (x).begin() + r
#define rsub(x, l, r) (x).rbegin() + l, (x).rbegin() + r
#define FOR(i, a, b) for (int i = a, _b = b; i <= _b; i++)
#define FORD(i, a, b) for (int i = a, _b = b; i >= _b; i--)

#define lcm(a, b) a / gcd(a, b) * b

#define Yes cout << "Yes\n";
#define No cout << "No\n";
#define YesNo Yes else No
#define NoYes No else Yes

template <class T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template <class T>
using max_heap = priority_queue<T, vector<T>, less<T>>;

#ifdef VanLam
#include <VanLam.h>
#define cer(...) debug_out(__VA_ARGS__)
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define __gcd(a, b) gcd(a, b)
#else
#define cer(...) 20
#define debug(...) 12
#define gcd(a, b) __gcd(a, b)
#endif

// #define int ll

const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
const int maxN = 1e6 + 5;

inline void prepare()
{
}

class Graph
{
public:
    int n;
    vvi adj;
    vi dp;

    Graph(int n)
    {
        this->n = n;
        adj.assign(n + 1, vi());
        dp.assign(n + 1, 0);
    }

    void addEdge(int u, int v)
    {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    void dfs(int u, int par = -1)
    {
        for (int v : adj[u])
        {
            if (v == par)
                continue;
            dfs(v, u);
            dp[u] += (dp[v] == 0);
        }
    }

    void reRoot(int u, int par = -1)
    {
        if (par != -1)
        {
            dp[u] += (dp[par] == 0);
        }

        for (int v : adj[u])
        {
            if (v == par)
                continue;
            int tmp = (dp[v] == 0);

            dp[u] -= tmp;
            reRoot(v, u);
            dp[u] += tmp;
        }
    }
};

inline void _VanLam_()
{
    int n, q;
    cin >> n >> q;

    Graph g(n);
    FOR(i, 1, n - 1)
    {
        int u, v;
        cin >> u >> v;
        g.addEdge(u, v);
    }

    g.dfs(1, -1);
    debug(g.dp);
    g.reRoot(1, -1);
    while (q--)
    {
        int root;
        cin >> root;
        if (g.dp[root])
        {
            cout << "Ron\n";
        }
        else
        {
            cout << "Hermione\n";
        }
    }
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    if (fopen("VanLam.inp", "r"))
    {
        freopen("VanLam.inp", "r", stdin);
        freopen("VanLam.out", "w", stdout);
    }

    prepare();

    int Case = 1;
    // cin >> Case;
    while (Case--)
    {
        cer("- - - -", Case, "- - - -");
        _VanLam_();
        cer("= = = = = = = = = =");
    }

    return 0;
}

H1. Harry Potter (Easy)

Solution

Code

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

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

#define ll long long
#define fi first
#define se second
#define vi vector<int>
#define vb vector<bool>
#define vc vector<char>
#define pii pair<int, int>
#define mii map<int, int>
#define mib map<int, bool>
#define vvi vector<vi>
#define vvb vector<vb>
#define vvc vector<vc>
#define vpi vector<pii>
#define vvpi vector<vpi>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sub(x, l, r) (x).begin() + l, (x).begin() + r
#define rsub(x, l, r) (x).rbegin() + l, (x).rbegin() + r
#define FOR(i, a, b) for (int i = a, _b = b; i <= _b; i++)
#define FORD(i, a, b) for (int i = a, _b = b; i >= _b; i--)

#define lcm(a, b) a / gcd(a, b) * b

#define Yes cout << "Yes\n";
#define No cout << "No\n";
#define YesNo Yes else No
#define NoYes No else Yes

template <class T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template <class T>
using max_heap = priority_queue<T, vector<T>, less<T>>;

#ifdef VanLam
#include <VanLam.h>
#define cer(...) debug_out(__VA_ARGS__)
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define __gcd(a, b) gcd(a, b)
#else
#define cer(...) 20
#define debug(...) 12
#define gcd(a, b) __gcd(a, b)
#endif

#define int ll

const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
const int maxN = 1e6 + 5;

inline void prepare()
{
}

inline void _VanLam_()
{
    int m, n;
    cin >> m >> n;

    vi s(m);
    FOR(i, 0, m - 1)
    cin >> s[i];
    vi l(m);
    FOR(i, 0, m - 1)
    cin >> l[i];
    vi t(m);
    FOR(i, 0, m - 1)
    t[i] = s[i] + l[i];

    vvi dp(2, vi(m, 0));
    dp[0][0] = 1;

    FOR(i, 1, n)
    {
        int T = 0, L = 0;
        FOR(j, 0, m - 1)
        {
            T += dp[(i - 1) & 1][j] * t[j] % MOD;
            L += dp[(i - 1) & 1][j] * l[j] % MOD;
            T %= MOD;
            L %= MOD;
        }

        FOR(j, 0, m - 1)
        {
            int TT = T * t[j] % MOD;
            int LL = L * l[j] % MOD;
            dp[i & 1][j] = (TT - LL + MOD) % MOD;
        }
    }

    int res = 0;
    FOR(j, 0, m - 1)
    {
        res += dp[n & 1][j];
        res %= MOD;
    }
    cout << res << "\n";
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    if (fopen("VanLam.inp", "r"))
    {
        freopen("VanLam.inp", "r", stdin);
        freopen("VanLam.out", "w", stdout);
    }

    prepare();

    int Case = 1;
    // cin >> Case;
    while (Case--)
    {
        cer("- - - -", Case, "- - - -");
        _VanLam_();
        cer("= = = = = = = = = =");
    }

    return 0;
}

H2. Harry Potter (Meium)

Solution

Code

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

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

#define ll long long
#define fi first
#define se second
#define vi vector<int>
#define vb vector<bool>
#define vc vector<char>
#define pii pair<int, int>
#define mii map<int, int>
#define mib map<int, bool>
#define vvi vector<vi>
#define vvb vector<vb>
#define vvc vector<vc>
#define vpi vector<pii>
#define vvpi vector<vpi>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sub(x, l, r) (x).begin() + l, (x).begin() + r
#define rsub(x, l, r) (x).rbegin() + l, (x).rbegin() + r
#define FOR(i, a, b) for (int i = a, _b = b; i <= _b; i++)
#define FORD(i, a, b) for (int i = a, _b = b; i >= _b; i--)

#define lcm(a, b) a / gcd(a, b) * b

#define Yes cout << "Yes\n";
#define No cout << "No\n";
#define YesNo Yes else No
#define NoYes No else Yes

template <class T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template <class T>
using max_heap = priority_queue<T, vector<T>, less<T>>;

#ifdef VanLam
#include <VanLam.h>
#define cer(...) debug_out(__VA_ARGS__)
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define __gcd(a, b) gcd(a, b)
#else
#define cer(...) 20
#define debug(...) 12
#define gcd(a, b) __gcd(a, b)
#endif

#define int ll

const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
const int maxN = 1e6 + 5;

inline void prepare()
{
}

struct Matrix
{
    int n, m;
    vvi matrix;

    Matrix(int n, int m)
    {
        this->n = n;
        this->m = m;
        matrix.assign(n, vi(m, 0));
    }
};

Matrix mulMatrix(const Matrix &a, const Matrix &b)
{
    Matrix res(a.n, b.m);
    FOR(i, 0, a.n - 1)
    {
        FOR(j, 0, b.m - 1)
        {
            FOR(k, 0, a.m - 1)
            {
                res.matrix[i][j] += a.matrix[i][k] * b.matrix[k][j] % MOD;
                res.matrix[i][j] %= MOD;
            }
        }
    }

    return res;
}

Matrix powMatrix(const Matrix &a, int k)
{
    if (k == 1)
        return a;
    Matrix res = powMatrix(a, k >> 1);
    res = mulMatrix(res, res);

    if (k & 1)
        res = mulMatrix(res, a);
    return res;
}

inline void _VanLam_()
{
    int m, n;
    cin >> m >> n;

    vi s(m);
    FOR(i, 0, m - 1)
    cin >> s[i];
    vi l(m);
    FOR(i, 0, m - 1)
    cin >> l[i];

    vi t(m);
    FOR(i, 0, m - 1)
    t[i] = s[i] + l[i];

    Matrix ans(m, m);
    FOR(i, 0, m - 1)
    {
        FOR(j, 0, m - 1)
        {
            ans.matrix[i][j] = (t[i] * t[j] % MOD - l[i] * l[j] % MOD + MOD) % MOD;
        }
    }

    ans = powMatrix(ans, n);
    int res = 0;
    FOR(j, 0, m - 1)
    {
        res += ans.matrix[0][j];
        res %= MOD;
    }
    cout << res;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    if (fopen("VanLam.inp", "r"))
    {
        freopen("VanLam.inp", "r", stdin);
        freopen("VanLam.out", "w", stdout);
    }

    prepare();

    int Case = 1;
    // cin >> Case;
    while (Case--)
    {
        cer("- - - -", Case, "- - - -");
        _VanLam_();
        cer("= = = = = = = = = =");
    }

    return 0;
}

H3. Harry Potter (Hard)

Solution

Code

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

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

#define ll long long
#define fi first
#define se second
#define vi vector<int>
#define vb vector<bool>
#define vc vector<char>
#define pii pair<int, int>
#define mii map<int, int>
#define mib map<int, bool>
#define vvi vector<vi>
#define vvb vector<vb>
#define vvc vector<vc>
#define vpi vector<pii>
#define vvpi vector<vpi>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sub(x, l, r) (x).begin() + l, (x).begin() + r
#define rsub(x, l, r) (x).rbegin() + l, (x).rbegin() + r
#define FOR(i, a, b) for (int i = a, _b = b; i <= _b; i++)
#define FORD(i, a, b) for (int i = a, _b = b; i >= _b; i--)

#define lcm(a, b) a / gcd(a, b) * b

#define Yes cout << "Yes\n";
#define No cout << "No\n";
#define YesNo Yes else No
#define NoYes No else Yes

template <class T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template <class T>
using max_heap = priority_queue<T, vector<T>, less<T>>;

#ifdef VanLam
#include <VanLam.h>
#define cer(...) debug_out(__VA_ARGS__)
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define __gcd(a, b) gcd(a, b)
#else
#define cer(...) 20
#define debug(...) 12
#define gcd(a, b) __gcd(a, b)
#endif

#define int ll

const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
const int maxN = 1e6 + 5;

inline void prepare()
{
}

struct Matrix
{
    int n, m;
    vvi matrix;

    Matrix(int n, int m)
    {
        this->n = n;
        this->m = m;
        matrix.assign(n, vi(m, 0));
    }
};

Matrix mulMatrix(const Matrix &a, const Matrix &b)
{
    Matrix res(a.n, b.m);
    FOR(i, 0, a.n - 1)
    {
        FOR(j, 0, b.m - 1)
        {
            FOR(k, 0, a.m - 1)
            {
                res.matrix[i][j] += a.matrix[i][k] * b.matrix[k][j] % MOD;
                res.matrix[i][j] %= MOD;
            }
        }
    }

    return res;
}

Matrix I(int n)
{
    Matrix res(n, n);
    FOR(i, 0, n - 1)
    res.matrix[i][i] = 1;
    return res;
}

Matrix powMatrix(const Matrix &a, int k)
{
    if (k == 0)
        return I(a.n);

    Matrix res = powMatrix(a, k >> 1);
    res = mulMatrix(res, res);

    if (k & 1)
        res = mulMatrix(res, a);
    return res;
}

inline void _VanLam_()
{
    int m, n;
    cin >> m >> n;

    vi s(m);
    FOR(i, 0, m - 1)
    cin >> s[i];
    vi l(m);
    FOR(i, 0, m - 1)
    cin >> l[i];

    vi t(m);
    FOR(i, 0, m - 1)
    t[i] = s[i] + l[i];

    Matrix B(m, 2);
    FOR(i, 0, m - 1)
    {
        B.matrix[i][0] = t[i];
        B.matrix[i][1] = l[i];
    }

    Matrix C(2, m);
    FOR(j, 0, m - 1)
    {
        C.matrix[0][j] = t[j];
        C.matrix[1][j] = MOD - l[j];
    }

    Matrix CB = mulMatrix(C, B);
    CB = powMatrix(CB, n - 1);

    Matrix ans = mulMatrix(B, CB);

    int res = 0;
    FOR(i, 0, m - 1)
    {
        int tmp = ans.matrix[0][0] * C.matrix[0][i] % MOD +
                  ans.matrix[0][1] * C.matrix[1][i] % MOD;
        tmp %= MOD;

        res += tmp;
        res %= MOD;
    }

    cout << res;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    if (fopen("VanLam.inp", "r"))
    {
        freopen("VanLam.inp", "r", stdin);
        freopen("VanLam.out", "w", stdout);
    }

    prepare();

    int Case = 1;
    // cin >> Case;
    while (Case--)
    {
        cer("- - - -", Case, "- - - -");
        _VanLam_();
        cer("= = = = = = = = = =");
    }

    return 0;
}

Full text and comments »

VanLam's blog

Ý tưởng chính

Bài toán con cần giải

Phân tích độ phức tạp

Ý tưởng tối ưu