10986 - 나머지 합

• 최적화 하는데서 좀 많이 헤맴.
• 처음에 아 걍 prefix sum이네! 하고 바로 짰는데 터짐.
• 간단하게 접근하면 제곱시간이 나오는데 그러면 시간초과나서 터짐.(제한시간 1초)
• 따라서 더 간단히 최적화할 방법을 찾아야함.
• $S_i$를 i까지의 부분합이라고 하자.
• 구간 i,j까지의 부분합이 M으로 나누어 떨어진다는것은 $S_j - S_{i-1} \equiv 0 \pmod{M}$이라는것이고, 정리하면 $S_j \equiv S_{i-1} \pmod{M}$.
• 따라서 나머지 합 문제는 나머지가 같은것 k개가 있다면 k중에 2개를 고르는 경우의 수를 구하는 문제로 바꿀수있다.

#include <iostream>
#include <vector>

using namespace std;

long long c[1001];
int main(void)
{
    std::ios::sync_with_stdio(false);
    long long result = 0;
    long long n,m,sum=0,temp;

    cin >> n >> m;
    c[0]=1; // 나머지가 0인 경우는 서로 다른 두개뿐만 아니라 자기자신을 뽑아도 되니 nC1 + nC2 = (n+1)C2  그러므로 초기값으로 1.
    for(int i = 0; i < n; i++) {
        cin >> temp;
        sum += temp;
        sum %= m;
        c[sum]++;
    }

    for(int i = 0; i < m; i++) {
        if(c[i])
            result += c[i] * (c[i]-1) / 2;
    }
    cout << result << endl;
}

• 문제가 막혔을경우 문제를 수식으로 표현하고 수학적인 도구들을 도입해서 최적화해나가는것을 알려준 괜찮은 문제였음.

드럽게 어렵네