Submission #523334

#	Time	Username	Problem	Language	Result	Execution time	Memory
523334		ac2hu	Modsum (NOI12_modsum)	C++14	25 / 25	1 ms	332 KiB

modsum

#include <bits/stdc++.h>
using namespace std;
signed main() {
	#define ll long long 
	iostream::sync_with_stdio(false);
	cin.tie(nullptr);cout.tie(nullptr);
	int n;cin >> n;
	vector<pair<int,int>> inp(n);
	for(auto &e : inp)
		cin >> e.first >> e.second;
	// We can solve this problem by finding the number of sums with k mod 5
	vector<array<int,5>> dp(n);
	vector<array<int,5>> count(n,{0,0,0,0,0});
	for(int i =0 ;i<n;i++){
		for(int j = inp[i].first;j<=inp[i].second;j++){
			count[i][(j%5)]++;
		}
	}
	// Calculating dp[0];
	for(int a1 = 0;a1<5;a1++)
		dp[0][a1] = count[0][a1];
	for(int i = 1;i<n;i++){
		dp[i] = {0,0,0,0,0};
		for(int al = 0;al<5;al++){
			for(int bl = 0;bl<5;bl++){
				dp[i][(al + bl)%5] += dp[i - 1][al]*count[i][bl];
			}
		}	
	}
	ll ans = 0;
	for(int al = 0;al<5;al++){
		if(al == 0)
			ans += dp[n - 1][al];
		else if(al == 1 || al == 4)
			ans += 4*dp[n - 1][al];
		else
			ans += 5*dp[n - 1][al];
	}
	cout << ans << "\n";
}

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