Quiz

https://atcoder.jp/contests/dwacon6th-prelims/tasks/dwacon6th_prelims_b

AC

https://atcoder.jp/contests/dwacon6th-prelims/submissions/9431139

解法

N=5の場合の順列（4! = 24通り）を全て描いて観察する

f:id:peroon:20200112072126j:plain

隣り合う丸の間（上記画像のアーチ）の本数を数える。すると、

f:id:peroon:20200112072712p:plain

（コンテスト中は24, 36, 44, 50を見て手が止まってしまった）
上記画像のように分解して法則をエスパーすると、各アーチの本数が数えられ、解ける
- ちゃんとした証明は解説放送にあります

Code

// a^b mod p
ll mod_pow(ll a, ll b){
    if(b==0) return 1;
 
    // 肩が奇数
    if(b%2==1){
        return a * mod_pow(a, b-1) % mod;
    }
    else{
        return mod_pow(a*a % mod, b/2) % mod;
    }
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N; 
    cin >> N;

    VI factorial(N+5, 0);
    factorial[0] = 1;
    factorial[1] = 1;
    FOR(i, 2, N+5){
      factorial[i] = factorial[i-1] * i % mod;
    }

    VI A(N);
    rep(i, N){
      cin >> A[i];
    }

    VI D;
    rep(i, N-1){
      ll d = A[i+1] - A[i];
      D.push_back(d);
    }

    ll sum = 0;
    ll F = factorial[N-1];
    ll a = 0;
    rep(i, N-1){

      // a += F/(i+1); // 割れない (modとってるから)
      a += F * mod_pow(i+1, mod-2); // 割る代わりに逆元
      
      a %= mod;
      sum += D[i] * a % mod;
      sum %= mod;
    }
    p(sum);

    return 0;
}