精美电影解题报告

目录er

• Description
• Input
• Output
• Sample Input
• Sample Output
• Data Constraint

Description

Diaoyeye作为一个健美先生，他决定观看精美电影。
Diaoyeye 一共有$n$部电影，每个电影都有一个时长。
由于Diaoyeye 没看过这些电影，所以Diaoyeye有可能喜欢或不喜欢这些电影。
若Diaoyeye现在已经看完了一部电影，如果Diaoyeye喜欢这部电影，那么他会增加等同于电影长度的健美值，并且如果他还没有收藏这部电影，那么他会把这个电影收藏起来；如果Diaoyeye不喜欢这部电影，那么他会降低等同于电影长度的健美值，并且会把之前收藏的电影再看一遍，来增加自己的健美值。
Diaoyeye已经想出了一个看精美电影的顺序，使得他期望增加的健美值最大。
Diaoyeye 想让你变得和他一样健美，所以他问你在这个顺序下期望增加的健美值对$1004535809$取模的值。

Input

第一行一个正整数$n$，意义如题。
接下来$n$行每行三个正整数 l i , x i , y i l_i,x_i,y_i li​,xi​,yi​，其中 l i l_i li​表示电影的长度， x i y i \frac{x_i}{y_i} yi​xi​​表示Diaoyeye 喜欢这部电影的概率。

Output

仅一个整数，表示你回答Diaoyeye的值。

Sample Input

2
1 1 2
2 1 2

Sample Output

502267905

Data Constraint

对于20%的数据，$n\le 5$。
对于50%的数据，$n\le 1000$。
另有20%的数据， l i l_i li​全都相等， x i x_i xi​全都相等， y i y_i yi​全都相等。
对于100%的数据， n ≤ 2 × 1 0 5 , 1 ≤ x i ≤ y i ≤ 1 0 6 , l i ≤ 1 0 6 n\leq2\times10^5,1\leq x_i\leq y_i\leq10^6,l_i\leq10^6 n≤2×105,1≤xi​≤yi​≤106,li​≤106。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！