結果

問題 No.1824 門＼松＼列
ユーザー tnakao0123tnakao0123
提出日時 2022-01-29 20:30:02
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 4 ms / 2,000 ms
コード長 1,077 bytes
コンパイル時間 425 ms
コンパイル使用メモリ 40,648 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-10 19:34:21
合計ジャッジ時間 1,035 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,812 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 4 ms
6,940 KB
testcase_04 AC 2 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

/* -*- coding: utf-8 -*-
 *
 * 1824.cc:  No.1824 門\松\列 - yukicoder
 */

#include<cstdio>
#include<algorithm>
 
using namespace std;

/* constant */

/* typedef */

typedef long long ll;

/* global variables */

/* subroutines */

inline ll sigma(int n) { return (ll)n * (n + 1) / 2; }
inline ll sigma2(int n) { return (ll)n * (n + 1) * (2 * n + 1) / 6; }

/* main */

int main() {
  int tn;
  scanf("%d", &tn);

  while (tn--) {
    int n;
    scanf("%d", &n);

    // sum_{i=1..n} { sum_{j=i+1..n} (j-2) + sum_{j=1..i-1} (n-j-1) }
    // = sum_{i=1..n} {(sigma(n)-sigma(i)-2(n-i)) + ((i-1)*n-sigma(i-1)-(i-1))}
    // = sum_{i=1..n} (sigma(n)-sigma(i)-2(n-i)+(i-1)(n-1)-sigma(i-1))
    // = sum_{i=1..n} (sigma(n)-2(n-i)+(i-1)(n-1)-i(i+1)/2-(i-1)i/2)
    // = sum_{i=1..n} (sigma(n)-2n+2i+(n-1)i-(n-1)-i^2)
    // = sum_{i=1..n} (sigma(n)-i^2+(n+1)i-(3n-1))
    // = n*sigma(n)-sigma2(n)+(n+1)sigma(n)-n*(3n-1)
    // = (2n+1)sigma(n)-sigma2(n)-n(3n-1)

    ll sum = sigma(n) * (n * 2 + 1) - sigma2(n) - (ll)n * (n * 3 - 1);
    printf("%lld\n", sum);
  }
  return 0;
}
0