글 읽기 - 모듈로 하는 문제에서 나머지연산 할 값을 한 번 더해주는 이유?

vegatrash 4년 전 0

이 문제가 정말정말 어려워서 결국 풀이보고 알고리즘은 다 이해하기는 했는데

코드에서 뭔가를 빼는 값에 MOD연산을 해줄 때 마다 빼기 전에 MOD할 값을 한 번 더해줘야 하는 이유를 잘 모르겠습니다....

이 더해주는것을 생략하면 자꾸 틀린 풀이라고 하는데 혹시 왜 더해주어야 하는지 아시는 분 계신가요?

아래는 http://www.usaco.org/current/data/sol_spainting_gold_jan18.html에도 나와있는 코드랑 거의 같은거긴 하지만 첨부합니다.

보시면 45번째 줄이랑 47번째 줄에서 나머지 연산하기전에 한 번 더해주는데
47번쨰 줄에서 보면 (ans + MOD - (s[N] - s[N - 1])) % MOD 에서 진하게 표시한것처럼 한 번 더해주는것을 생략하면 틀리더라고요...

아 물론 a mod b == (a + b) mod b인건 알기는 하지만 저기서 MOD를 안더해주면 틀리는 이유가 뭘까요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string>
#include <vector>
#include <queue>
#include <list>
#include <time.h>
#include <memory.h>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#include <list>
#define MOD 1000000007
using namespace std;

typedef long long ll;

ll s[1000001];

ll myPower(ll a, ll b) {
	if (b == 0) return 1;
	if (b == 1) return a;

	if (b % 2 == 0) return (myPower(a, b / 2) * myPower(a, b / 2)) % MOD;
	else return ((myPower(a, (b - 1) / 2) * myPower(a, (b - 1) / 2)) % MOD * a) % MOD;
}

int main(void)
{
	cin.sync_with_stdio(false);
	cout.sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	ll N, M, K, ans;
	cin >> N >> M >> K;
	ans = myPower(M, N);
	s[0] = 0;
	for (int i = 1; i < K; i++) {
		s[i] = (s[i - 1] * M + M) % MOD;
	}
	for (int i = K; i <= N; i++) {
		s[i] = (M * (s[i - 1]) + MOD - ((M - 1) * (s[i - K])) % MOD) % MOD;
	}
	cout << (ans + MOD - (s[N] - s[N - 1])) % MOD;
}