大神的世界

這題不是我自己想的，程式也是

程式源自 https://sites.google.com/site/silithusxoi/code/ks2014

如有違反著作權，煩請告知

這邊我單純分析他的想法和程式

首先，如果用暴力法算出每個區段, 必定 TLE   ( 共有 n + (n-1) + (n-2) + ... + 1 個連續區段 )

他的想法是兩相同餘數間的美好度和，必定為 P/Q 的整數倍

以他的例子來說，1 4 6 有相同的餘數

所以 2~4 , 5~6 的美好度和，為 P/Q 的整數倍

為什麼呢？

因為加入 2 3 4 的美好度後，餘數不變

代表 2 3 4 的平均美好度必定餘 0 , 因此為 P/Q 的整數倍

至於 e 說的要考慮 0/0 的意思是

餘數為 0/0 代表從第一棵到該棵依舊是 P/Q 的整數倍

以他的例子來說就是 1~2 棵

所以共有 4 種可能 ( 1~2, 2~4, 5~6, 2~6 )

#include <cstdio>
#include <algorithm>

#define LL long long

using namespace std;

// pq 用來紀錄餘數

struct one_pq {
    LL p;
    int q;

    bool operator< (const one_pq &v) {
        return ( (q == v.q) ? (p < v.p) : (q < v.q) );
    }
    bool operator!= (const one_pq &v)  {
        return ( p!=v.p || q!=v.q );
    }
};

one_pq pq[1000002];

int main()
{
    int N,P,Q,i,c;
    LL g,sum,ans;
    
    scanf("%d %d %d", &N, &P, &Q);

    // a. 化為最簡分數
    c = __gcd(P,Q);
    P /= c;
    Q /= c;

    // b. 計算餘數

    for(i=1,sum=0ll; i<=N; i++) {
        scanf("%d", &c);
        sum += c;
        g = i / Q;     // 累計美好度的分母 (也就是棵數) 是 Q 的幾倍
        if( P != 0ll )   // 如果 P == 0 ，則考慮分母的倍率即可, 但如果 P != 0 , 用分母的倍率可能會把 p 減成負的
            g = min(g, sum/P);  // 因此選 g 為分母或分子的最小倍率
        pq[i].p = (sum - P*g);
        pq[i].q = (int)(i - Q*g);
    }

   // 將餘數排序，一則讓相同餘數聚在一起，好計算有幾區，另一則是讓 0/0 出現在最前面方便計算

    sort(pq+1, pq+1+N);     // sort 是內建函數，比較方式會依照他上面定義的方式 (operator overloading)
    pq[0].p = 0ll; pq[0].q = 0;
    pq[N+1].p = -1ll; pq[N+1].q = -1;

    // d. 計算區域數

    ans = 0ll;
    for(i=1,c=0; i<=N+1; i++) {
        if( pq[i] != pq[c] ) {
            g = i - c - 1;   // 2/1 共有 3 個，所以有 2 區 (2~4 和 5~6)  i = 6, c = 3
            ans += (g+1) * g / 2;   // g + (g-1) + ... + 1
            c = i;
        }
    }
        
    printf("%lld\n", ans);

    return 0;
}