fork download 
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. #define ll long long
  6.  
  7. const ll MOD = 998244353;
  8.  
  9. ll binpow(ll x, ll y) {
  10. 	if (y == 0) return 1;
  11. 	ll res = binpow(x, y / 2);
  12. 	res = res * res % MOD;
  13. 	if (y & 1) res = res * x % MOD;
  14. 	return res;
  15. }
  16.  
  17. ll inv(ll x) {
  18. 	return binpow(x, MOD - 2);
  19. }
  20.  
  21. int main() {
  22. 	cin.tie(0)->sync_with_stdio(0);
  23. 	int n, m; cin >> n >> m;
  24. 	vector<vector<pair<int, ll>>> arr(m + 1); // arr[right endpt] = {length of segment, p * inv(q) % MOD}
  25.  
  26. 	vector<ll> psum(m + 1, 1);
  27. 	for (int i = 0; i < n; i++) {
  28. 		int l, r; ll p, q;
  29. 		cin >> l >> r >> p >> q;
  30.  
  31. 		ll mul = p * inv(q) % MOD;
  32. 		arr[r].push_back({r - l + 1, mul});
  33. 		psum[l] = psum[l] * (1 - mul + MOD) % MOD; // (1 - p/q)
  34. 	}
  35.  
  36. 	for (int i = 1; i <= m; i++) {
  37. 		psum[i] = psum[i - 1] * psum[i] % MOD;
  38. 	}
  39.  
  40. 	vector<ll> dp(m + 1, 0);
  41. 	dp[0] = 1;
  42. 	for (int i = 1; i <= m; i++) {
  43. 		for (auto [len, mul] : arr[i]) {
  44. 			int j = i - len; 
  45.  
  46. 			// dp[j] * (psum[i] / psum[j]) / (1 - mul) * mul
  47. 			dp[i] = (dp[i] + dp[j] * psum[i] % MOD * inv(psum[j]) % MOD * inv((1 - mul + MOD) % MOD) % MOD * mul % MOD) % MOD;
  48. 		}
  49. 	}
  50. 	cout << dp[m] << '\n';
  51. 	return 0;
  52. }
  53.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin 
8 5
1 3 1 2
1 5 1 6
1 4 4 5
5 5 1 7
4 5 1 2
4 5 2 5
3 3 2 7
1 2 1 3
stdout 
94391813
https://ideone.com/butZtq
language:
C++ (gcc 8.3)
created:
6 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!