QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#618643#9442. Music GameAPROHACK124WA 0ms7664kbC++141.9kb2024-10-07 01:49:212024-10-07 01:49:22

Judging History

你现在查看的是最新测评结果

  • [2024-10-07 01:49:22]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:7664kb
  • [2024-10-07 01:49:21]
  • 提交

answer

#include<bits/stdc++.h>

#define pb push_back
#define pii pair<int,int>
#define ff first
#define ss second

using ll = long long;
using lf = long double;
using namespace std;
int n;
const int mod = 998244353;
ll multi(ll a, ll b){
    return a * b % mod;
}
ll sume(ll a, ll b){
    return (a + b) % mod;
}

ll fast_expo(ll base, ll exp){
    if(exp == 0)return 1;
    ll temp = fast_expo(base, exp / 2);
    if(exp % 2 == 0)return temp * temp % mod;
    return temp * temp % mod * base % mod;
}

ll mod_inv(ll k){
    return fast_expo(k, mod - 2);
}
ll t[200005], p[200005], q[200005];
vector<pair<pair<ll, ll>, ll > > v;

ll expected(ll qq, ll pp){
    return multi(qq, mod_inv(multi(pp,pp)));
}

bool cmp(pair<pair<ll, ll>, ll>a, pair<pair<ll, ll>, ll> b){
    // a < b if
    ll mul1 = a.ff.ff * b.ff.ss;
    ll mul2 = a.ff.ss * b.ff.ff;
    if( mul1 < mul2 )return true;
    if(mul1 > mul2)return false;
    return a.ss < b.ss;
}


int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    #ifdef LOCAL
    freopen("in", "r", stdin);
    #endif
    cin >> n;
    for(int i = 0 ; i < n ; i++){
        ll a, b;
        cin >> t[i] >> a >> b;
        p[i] = a * mod_inv(b) % mod;
        q[i] = (b - a) * mod_inv(b) % mod;
        v.pb({{a, b}, t[i]});
    }
    sort(v.begin(), v.end(), cmp);
    for(int i = 0 ; i < n ; i ++){
        ll a = v[i].ff.ff;
        ll b = v[i].ff.ss;
        p[i] = a * mod_inv(b) % mod;
        q[i] = (b - a) * mod_inv(b) % mod;
        t[i] = v[i].ss;
    }

    ll ans = 0;
    ll tempo = 0;
    ll acum = 1;

    for(int i = 0 ; i < n ; i ++){
        acum = multi(acum, p[i]);
        tempo = sume(t[i], tempo);
        ans = sume(ans, multi(tempo, expected(q[i], p[i])));
    }

    ans = sume(ans, multi(tempo, acum));
    if(ans < 0)ans += mod;
    cout << ans << "\n";


    
    return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 7664kb

input:

2
3 3 5
2 4 7

output:

881386393

result:

wrong answer 1st words differ - expected: '831870305', found: '881386393'