結果
問題 |
No.125 悪の花弁
|
ユーザー |
|
提出日時 | 2024-03-08 16:44:33 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 27 ms / 5,000 ms |
コード長 | 1,135 bytes |
コンパイル時間 | 1,965 ms |
コンパイル使用メモリ | 193,424 KB |
最終ジャッジ日時 | 2025-02-20 01:49:36 |
ジャッジサーバーID (参考情報) |
judge4 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 6 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:22:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 22 | scanf("%d", &n); | ~~~~~^~~~~~~~~~ main.cpp:24:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 24 | scanf("%d", &a[i]); | ~~~~~^~~~~~~~~~~~~
ソースコード
#include <bits/stdc++.h> const int N = 1e5 + 7; const int M = 1e6 + 7; const int MOD = 1e9 + 7; int fac[M], ifc[M], n, a[N], f[N], d[N], cd; int pow(int x, int y) { int ret = 1; while(y) { if(y & 1) ret = 1LL * ret * x % MOD; x = 1LL * x * x % MOD; y >>= 1; } return ret; } int main() { scanf("%d", &n); for(int i = 1; i <= n; ++i) scanf("%d", &a[i]); int sum = 0, g = 0; for(int i = 1; i <= n; ++i) { sum += a[i]; g = std::__gcd(g, a[i]); } fac[0] = 1; for(int i = 1; i <= sum; ++i) fac[i] = 1LL * fac[i - 1] * i % MOD; ifc[sum] = pow(fac[sum], MOD - 2); for(int i = sum - 1; i >= 0; --i) ifc[i] = 1LL * ifc[i + 1] * (i + 1) % MOD; for(int i = 1; i <= g; ++i) if(g % i == 0) d[++cd] = i; int ans = 0; for(int i = cd; i >= 1; --i) { f[i] = fac[sum / d[i]]; for(int j = 1; j <= n; ++j) f[i] = 1LL * f[i] * ifc[a[j] / d[i]] % MOD; for(int j = cd; j > i; --j) if(d[j] % d[i] == 0) f[i] = (f[i] + MOD - f[j]) % MOD; ans = (ans + 1LL * f[i] * pow(sum / d[i], MOD - 2)) % MOD; } printf("%d\n", ans); return 0; }