結果

問題 No.125 悪の花弁
ユーザー akusyounin2412akusyounin2412
提出日時 2019-09-26 22:15:05
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 3,636 bytes
コンパイル時間 1,275 ms
コンパイル使用メモリ 129,732 KB
実行使用メモリ 29,020 KB
最終ジャッジ日時 2024-09-24 06:25:26
合計ジャッジ時間 7,636 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 AC 718 ms
25,288 KB
testcase_02 AC 954 ms
27,632 KB
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

# include <iostream>
# include <algorithm>
#include <array>
# include <cassert>
#include <cctype>
#include <climits>
#include <numeric>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <tuple>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <bitset>
# include <complex>
# include <chrono>
# include <random>
# include <limits.h>
# include <unordered_map>
# include <unordered_set>
# include <deque>
# include <cstdio>
# include <cstring>
#include <stdio.h>
#include<time.h>
#include <stdlib.h>
#include <cstdint>
#include <cfenv>
#include<fstream>
//#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
long long MOD = 1000000000 + 7;//998244353;
constexpr long long INF = numeric_limits<LL>::max() / 2;
const double PI = acos(-1);
#define fir first
#define sec second
#define thi third
#define debug(x) cerr<<#x<<": "<<x<<'\n'
typedef pair<LL, LL> Pll;
typedef pair<LL, pair<LL, LL>> Ppll;
typedef pair<LL, pair<LL, bitset<100001>>> Pbll;
typedef pair<LL, pair<LL, vector<LL>>> Pvll;
typedef pair<LL, LL> Vec2;
struct Tll { LL first, second, third; };
struct Fll { LL first, second, third, fourd; };
typedef pair<LL, Tll> Ptll;
#define rep(i,rept) for(LL i=0;i<rept;i++)
#define Rrep(i,mf) for(LL i=mf-1;i>=0;i--)
void YN(bool f) {
	if (f)
		cout << "YES" << endl;
	else
		cout << "NO" << endl;
}
void yn(bool f) {
	if (f)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
}
struct Edge { LL to, cost; };
struct edge { LL from, to, cost; };
vector<vector<int>>g;
vector<edge>edges;
vector<Pll>v;
map<Pll, Pll>ma;
set<LL>st;
LL h, w, n, m, k, t, s, p, q, last, cnt, sum, ans, a[210000], b[210000], dp[1000100];
string str, ss;
bool f;
char c;
int di[4][2] = { { 0,1 },{ 1,0 },{ 0,-1 },{ -1,0 } };
LL gcd(LL a, LL b) {
	if (a < b) gcd(b, a);
	LL r;
	while ((r = a % b)) {
		a = b;
		b = r;
	}
	return b;
}
struct Combination {
	int mod;
	vector< int64_t > mfact, rfact;

	Combination(int sz, int mod) : mfact(sz + 1), rfact(sz + 1), mod(mod) {
		mfact[0] = 1;
		for (int i = 1; i < mfact.size(); i++) {
			mfact[i] = mfact[i - 1] * i % mod;
		}
		rfact[sz] = inv(mfact[sz]);
		for (int i = sz - 1; i >= 0; i--) {
			rfact[i] = rfact[i + 1] * (i + 1) % mod;
		}
	}

	int64_t fact(int k) const {
		return (mfact[k]);
	}

	int64_t pow(int64_t x, int64_t n = MOD - 2) const {
		int64_t ret = 1;
		while (n > 0) {
			if (n & 1) (ret *= x) %= mod;
			(x *= x) %= mod;
			n >>= 1;
		}
		return (ret);
	}

	int64_t inv(int64_t x) const {
		return (pow(x, mod - 2));
	}

	int64_t P(int n, int r) const {
		if (r < 0 || n < r) return (0);
		return (mfact[n] * rfact[n - r] % mod);
	}

	int64_t C(int p, int q) const {
		if (q < 0 || p < q) return (0);
		return (mfact[p] * rfact[q] % mod * rfact[p - q] % mod);
	}

	int64_t H(int n, int r) const {
		if (n < 0 || r < 0) return (0);
		return (r == 0 ? 1 : C(n + r - 1, r));
	}
};
Combination comb(1000010, MOD);
int main() {
	cin >> n;
	LL gcd_=-1;
	rep(i, n) {
		cin >> a[i];
		sum += a[i];
		if (gcd_ == -1) {
			gcd_ = a[i];
		}
		else gcd_ = gcd(gcd_, a[i]);
	}
	for (int i = 1; i <= sum; i++) {
		if (gcd_%i == 0) {
			LL num = sum / i;
			cnt = 1;
			rep(j, n) {
				cnt *= comb.C(num, a[j] / i);
				num -= a[j] / i;
				cnt %= MOD;
			}
			dp[i] = cnt;
		}
	}
	for (int i = sum; i >=1; i--) {
		for (int j = 2; j*i <= sum; j++) {
			dp[i] -= dp[j*i] * (j);
			dp[i] += MOD;
			dp[i] %= MOD;
		} 
		dp[i] *= comb.pow(sum / i);
		dp[i] %= MOD;
		ans += (dp[i]);
		ans %= MOD;
	}
	cout << ans << endl;
	return 0;
}
0