結果

問題 No.2369 Some Products
コンテスト
ユーザー vjudge1
提出日時 2026-03-12 23:06:43
言語 C++14
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++14 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 304 ms / 2,500 ms
コード長 1,252 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 532 ms
コンパイル使用メモリ 78,076 KB
実行使用メモリ 168,448 KB
最終ジャッジ日時 2026-03-12 23:06:53
合計ジャッジ時間 3,341 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<iostream>
using namespace std;
// #define int long long
const int N = 5005;
const int mod = 998244353;

int n,p[N],q,f[N][N],r[N],pre[N],g[N][N];

int qpow(int a,int b)
{
	int res = 1;
	while(b)
	{
		if(b & 1) res = 1ll * res * a % mod;
		a = 1ll * a * a % mod; b >>= 1;
	}
	return res;
}

signed main()
{
	cin >> n; for(int i=1;i<=n;i++) cin >> p[i], p[i] = (mod + p[i] % mod) % mod;
	f[0][0] = 1;
	for(int i=1;i<=n;i++)
	{
		f[i][i] = 1ll * f[i-1][i-1] * p[i] % mod; f[i][0] = f[i-1][0];
		for(int j=1;j<i;j++) f[i][j] = (1ll * f[i-1][j-1] * p[i] + f[i-1][j]) % mod;
	}
	pre[0] = 1;
	for(int i=0;i<n;i++)
		for(int j=i+1;j>=1;j--)
			pre[j] = (pre[j] + 1ll * p[i+1] * pre[j-1]) % mod;
	r[0] = 1;
	for(int i=1;i<=n;i++)
	{
		int sum = 0;
		for(int j=1;j<=i;j++) sum = (sum + 1ll * pre[j] * r[i-j]) % mod;
		r[i] = (mod - sum) % mod;
	}
	g[n][0] = r[0];
	for(int i=1;i<=n;i++) g[n][i] = (r[i] + 1ll * r[i-1] * p[n]) % mod;
	for(int i=n-1;i>=1;i--)
	{
		g[i][0] = g[i+1][0];
		for(int j=1;j<=n;j++)
			g[i][j] = (g[i+1][j] + 1ll * p[i] * g[i+1][j-1]) % mod;
	}
	cin >> q;
	while(q--)
	{
		int a, b, k; cin >> a >> b >> k; int ans = 0;
		for(int i=0;i<=k;i++) ans = (ans + 1ll * f[b][i] * g[a][k-i]) % mod;
		cout << ans << '\n';
	}
	return 0;
}
0