結果

問題 No.1510 Simple Integral
ユーザー catuppercatupper
提出日時 2021-05-15 02:46:15
言語 C++17(clang)
(17.0.6 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,827 bytes
コンパイル時間 1,099 ms
コンパイル使用メモリ 145,468 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-04-10 07:27:51
合計ジャッジ時間 2,675 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 1 ms
6,944 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 1 ms
6,940 KB
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 AC 9 ms
6,944 KB
testcase_24 AC 9 ms
6,940 KB
testcase_25 AC 9 ms
6,944 KB
testcase_26 AC 9 ms
6,944 KB
testcase_27 AC 9 ms
6,944 KB
testcase_28 AC 9 ms
6,940 KB
testcase_29 AC 9 ms
6,940 KB
testcase_30 AC 9 ms
6,940 KB
testcase_31 AC 9 ms
6,944 KB
testcase_32 AC 9 ms
6,940 KB
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
testcase_38 WA -
testcase_39 WA -
testcase_40 WA -
testcase_41 WA -
testcase_42 WA -
testcase_43 AC 2 ms
6,940 KB
testcase_44 WA -
testcase_45 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <cmath>
#include <complex>
#include <cstdio>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
using Int = long long;
using Real = long double;
using CP = complex<Real>;
using P = pair<Int, Int>;

const Int MOD = 1000000007;
const Int MOD2 = 998244353;
const Int LINF = (1LL << 60);
const int INF = (1000000007);
const Real EPS = 1e-10;
const long double PI = 3.141592653589793238462643383279502884L;

Int modpow(Int a, Int b){
  if(b == 0)return 1;
  if(b % 2)return modpow(a, b-1) * a % MOD2;
  auto half = modpow(a, b / 2);
  return half * half % MOD2;
}

Int inv(Int x){
  return modpow(x, MOD2 - 2);
}

int main()
{
  Int n, a;
  cin >> n;
  map<Int, Int> cnt;
  vector<Int> as;
  for(int i = 0;i < n;i++){
    cin >> a;
    cnt[a]++;
    as.push_back(a);
  }
  Int ans = 0;
  for(auto [x, x_cnt]:cnt){
    vector<Int> val(x_cnt, 0);
    val[0] = 1;
    for(auto a:as){
      for(int i = x_cnt - 1;i >= 0;i--){
	Int tmp = 0;
	Int inv_x_a = inv(x+a);
	Int prod = inv_x_a;
	Int fact = 1;
	for(int j = 0;i - j >= 0;j++){
	  (tmp += val[i-j] * prod % MOD2 * fact %MOD2 * ((j % 2 == 1) ? -1 : 1)) %= MOD2;
	  (prod *= inv_x_a) %= MOD2;
	  (fact *= (j+1))%=MOD2;
	}
	val[i] = tmp;
      }
      if(a != x){
	for(int i = x_cnt - 1;i >= 0;i--){
	  Int tmp = 0;
	  Int inv_x_a = inv(x-a);
	  Int prod = inv_x_a;
	  Int fact = 1;
	  for(int j = 0;i - j >= 0;j++){
	    (tmp += val[i-j] * prod % MOD2 * fact %MOD2 * ((j % 2 == 1) ? -1 : 1)) %= MOD2;
	    (prod *= inv_x_a) %= MOD2;
	    (fact *= (j+1))%=MOD2;
	  }
	  val[i] = tmp;
	}
      }
    }
    (ans += val.back()) %= MOD2;
  }
  ans *= 2;
  ans %= MOD2;
  if(n % 2 == 0)ans = (MOD2 - ans) % MOD2;
  cout << ans << endl;
  return 0;
}
0