はまやんはまやんはまやん

hamayanhamayan's blog

ModSum [AtCoder Beginner Contest 139 D]

https://atcoder.jp/contests/abc139/tasks/abc139_d

解説

https://atcoder.jp/contests/abc139/submissions/7339048

Nの上限が109なので、Nに起因するアルゴリズムではなさそう。
それで400点ということもあり、特殊な解法が存在するっぽい。

という訳で実験してみよう。

N     ans    P  
1     0      1  
2     1      2 1  
3     3      1 3 2  
             2 3 1  
4     6      2 3 4 1  
5     10     1 3 4 5 2  
             2 1 4 5 3  
             2 3 4 5 1  

2 3 4 ... N 1のようにしていけばいいっぽい。
こうすると、1+2+3+...+(N-1)が得られる。
つまり、(N-1)*N/2が答え。

ll N;
//---------------------------------------------------------------------------------------------------
void labo(int n) {
    vector<int> v;
    rep(i, 0, n) v.push_back(i + 1);
    do {
        int tot = 0;
        rep(i, 0, n) tot += (i + 1) % v[i];
        printf("%d", tot);
        rep(i, 0, n) printf(" %d", v[i]);
        printf("\n");
    } while (next_permutation(all(v)));
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    ll ans = (N - 1) * N / 2;
    cout << ans << endl;
}