結果
問題 | No.1510 Simple Integral |
ユーザー |
![]() |
提出日時 | 2021-05-15 01:09:05 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 13 ms / 2,000 ms |
コード長 | 2,880 bytes |
コンパイル時間 | 6,890 ms |
コンパイル使用メモリ | 267,584 KB |
最終ジャッジ日時 | 2025-01-21 12:55:06 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 43 |
ソースコード
#include <bits/stdc++.h>using namespace std;#include "atcoder/all"using namespace atcoder;using Mint = modint998244353;vector c(300, vector(300, Mint{1}));vector seen(300, vector(300, false));Mint C(int n, int k) {if (k < 0 || k > n)return 0;if (seen[n][k])return c[n][k];seen[n][k] = true;auto& ret = c[n][k];if (n == 0)return ret = 1;return ret = C(n - 1, k) + C(n - 1, k - 1);}int main() {int N;cin >> N;vector<int> A(N);map<int, int> mp;for (auto&& a : A) {cin >> a;mp[a]++;}vector<pair<int, int>> V;for (auto p : mp) {V.push_back(p);}Mint ans = 0;for (auto&& [a, n] : V) {Mint book = 1;vector<Mint> memo(n);memo[0] = 1;for (auto&& [b, m] : V) {if (b != a) {{vector<Mint> memo_nxt(n);for (int i = 0; i <= n - 1; i++) {Mint tmp = Mint{1} / Mint{a + b}.pow(m);for (int j = 0;; j++) {if (i + j > n - 1)break;//j回微分memo_nxt[i + j] += memo[i] * tmp * C(i + j, j);tmp *= -(m + j);tmp /= (a + b);}}swap(memo, memo_nxt);}{vector<Mint> memo_nxt(n);for (int i = 0; i <= n - 1; i++) {Mint tmp = Mint{1} / Mint{a - b}.pow(m);for (int j = 0;; j++) {if (i + j > n - 1)break;//j回微分memo_nxt[i + j] += memo[i] * tmp * C(i + j, j);tmp *= -(m + j);tmp /= (a - b);}}swap(memo, memo_nxt);}}}{vector<Mint> memo_nxt(n);for (int i = 0; i <= n - 1; i++) {Mint tmp = Mint{1} / Mint{2 * a}.pow(n);for (int j = 0;; j++) {if (i + j > n - 1)break;//j回微分memo_nxt[i + j] += memo[i] * tmp * C(i + j, j);tmp *= -(n + j);tmp /= (2 * a);}}swap(memo, memo_nxt);}book = memo[n - 1];for (int i = 1; i <= n - 1; i++) {book /= i;}ans += book;}ans *= 2;if (N % 2 == 0)ans *= -1;cout << ans.val() << endl;}