結果
問題 | No.1067 #いろいろな色 / Red and Blue and more various colors (Middle) |
ユーザー |
|
提出日時 | 2020-05-29 22:44:16 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,123 ms / 2,000 ms |
コード長 | 678 bytes |
コンパイル時間 | 374 ms |
コンパイル使用メモリ | 82,116 KB |
実行使用メモリ | 359,696 KB |
最終ジャッジ日時 | 2024-11-06 06:40:35 |
合計ジャッジ時間 | 10,142 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 25 |
ソースコード
import bisect N, Q = map(int, input().split()) A = sorted(list(map(int, input().split())), reverse=True) MOD = 998244353 dp = [[0] * (N + 2) for _ in range(N + 1)] dp[0][1] = 1 for i, a in enumerate(A): for j in range(1, N + 2): dp[i + 1][j] += dp[i][j] * (a - 1) + dp[i][j - 1] dp[i + 1][j] %= MOD t = 1 for i, a in enumerate(reversed(A)): t = (t * a) % MOD for j in range(N + 2): dp[N - 1 - i][j] = dp[N - 1 - i][j] * t % MOD Am = [-a for a in A] for _ in range(Q): l, r, p = map(int, input().split()) ans = 0 for i in range(l, r + 1): y = bisect.bisect_right(Am, -i) ans ^= dp[y][p+1] print(ans % MOD)