Submission #1137027

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137027		sohamsen15	Modsum (NOI12_modsum)	C++20	25 / 25	4 ms	1096 KiB

modsum

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

vector<map<ll, ll>> c;
map<pll, ll> memo;

ll f(ll k, ll n) {
    if (memo.count({k, n})) return memo[{k, n}];
    if (n == 0) return c[n][k];
    ll ans = 0; 
    for (ll i = 0; i < 5; i++)
        ans += c[n][i] * f((5 + k - i) % 5, n - 1);
    memo[{k, n}] = ans;
    return ans;
}

ll g(ll n) {
    return 1 + (n * n * n * n + 2 * n * n) % 5;
}

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

    ll n; cin >> n; c.resize(n);
    vector<ll> v(n), w(n);
    for (ll i = 0; i < n; i++) cin >> v[i] >> w[i];

    for (ll i = 0; i < n; i++)
        for (ll j = 0; j < 5; j++)
            c[i][j] = 0;

    for (ll i = 0; i < n; i++) 
        for (ll j = v[i]; j <= w[i]; j++) 
            c[i][j % 5]++;

    ll ans = 0;
    for (ll i = 0; i < 5; i++)
        ans += f(i, n - 1) * g(i);

    cout << ans;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5