Submission #1258598

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258598		phtung	Modsum (NOI12_modsum)	C++20	25 / 25	811 ms	16108 KiB

modsum

#include <bits/stdc++.h>

using namespace std;

#define name "IO"
#define int long long 

const int mod = 5;
const int inf = 1e18 + 7; 
const int maxn = 1e6 + 5; 
int n;

int Pow(int x, int y) 
{
    int ans = 1;
    while (y > 0) 
    {
        if (y & 1) ans = (ans * x) % mod;
        y /= 2;
        x = x * x;
        x %= mod;
    }
    return ans;
}


int f(int sum)
{
    int s2 = (sum % 5) * (sum % 5) % 5; 
    int s4 = (s2 * s2) % 5;
    return ((s4 + 2 * s2) % 5) + 1;
}


void solve()
{
    int n;
    cin >> n;
    
    vector<pair<int,int>> range(n); 
    for(int i = 0; i < n; i++)
    {
        int l, r;
        cin >> l >> r; 
        range[i] = {l, r}; 
    }

    vector<int> dp(maxn, 0);
    dp[0] = 1; 

    for(auto [l, r] : range)
    {
        vector<int> new_dp(maxn, 0); 
        for(int s = 0; s <= maxn - 5; s++)
        {
            if(!dp[s]) continue; 
            for(int val = l; val <= r; val++)
            {
                new_dp[s + val] += dp[s]; 
            }
        }
        dp.swap(new_dp); 
    }

    int res = 0 ;
    for(int sum = 0; sum <= maxn - 5; sum++)
    {
        if(dp[sum])
        {
            res += dp[sum] * f(sum); 
        }
    }

    cout << res << "\n"; 

}

signed main()
{
    if (fopen (name".INP", "r"))
    {
        freopen (name".INP", "r", stdin);
        freopen (name".OUT", "w", stdout);
    }

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    clock_t start = clock(); 

    int t = 1;

    while(t--) solve(); 

    std::cerr << "Time: " << clock() - start << "ms\n";

    return 0; 

}

Compilation message (stderr)

modsum.cpp: In function 'int main()':
modsum.cpp:82:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |         freopen (name".INP", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
modsum.cpp:83:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |         freopen (name".OUT", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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