第6回 ドワンゴからの挑戦状 予選 B Fusing Slimes
第6回 ドワンゴからの挑戦状 予選 B Fusing Slimes
問題概要
リンク参照
ソースコード
#include<algorithm> #include<bitset> #include<cassert> #include<cfloat> #include<climits> #include<cmath> #include<deque> #include<functional> #include<iomanip> #include<iostream> #include<map> #include<queue> #include<set> #include<stack> #include<string> #include<unordered_map> #include<unordered_set> #include<utility> #include<vector> using namespace std; typedef long long int ll; const ll MOD = 1e9 + 7; /******************************************************************************************/ struct Combination { vector<ll> fact, rfact; Combination(ll sz) : fact(sz + 1), rfact(sz + 1) { fact[0] = 1; for (ll i = 1; i < fact.size(); i++) { fact[i] = fact[i - 1] * i % MOD; } //逆元 rfact[sz] = inv(fact[sz]); for (ll i = sz - 1; i >= 0; i--) { rfact[i] = rfact[i + 1] * (i + 1) % MOD; } } ll inv(ll x) { return pow(x, MOD - 2); } ll pow(ll x, ll n) { ll ret = 1; while (n > 0) { if (n & 1) (ret *= x) %= MOD; (x *= x) %= MOD; n >>= 1; } return (ret); } ll P(ll n, ll r) { if (r < 0 || n < r) return (0); return (fact[n] * rfact[n - r] % MOD); } ll C(ll p, ll q) { if (q < 0 || p < q) return (0); return (fact[p] * rfact[q] % MOD * rfact[p - q] % MOD); } ll H(ll n, ll r) { if (n < 0 || r < 0) return (0); return (r == 0 ? 1 : C(n + r - 1, r)); } }; int main() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(10); int n; cin >> n; Combination comb(n + 10); vector<ll> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } ll p = 1LL; for (ll i = 1; i < n; i++) { p *= i; p %= MOD; } ll ans = 0; ll tm = 0; for (int i = 0; i < n - 1 ; i++) { ll diff = a[i + 1] - a[i]; tm += comb.inv(i + 1LL); tm %= MOD; ans += diff * tm; ans %= MOD; } cout << (ans*p)%MOD<< endl; return 0; }