QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#372133 | #3006. Heaps of Fun | InfinityNS# | WA | 1ms | 4324kb | C++14 | 2.2kb | 2024-03-30 23:25:22 | 2024-03-30 23:25:22 |
Judging History
answer
#include<bits/stdc++.h>
#define pb push_back
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x).size()
#define f first
#define s second
#define ll long long
using namespace std;
const int mod=1e9+7;
int add(int x,int y){
x+=y;
if(x>=mod)x-=mod;
return x;
}
int sub(int x,int y){
x-=y;
if(x<0)x+=mod;
return x;
}
int mul(int x,int y){
return (ll)x*y%mod;
}
int pwrmod(int x,int k){
int ans=1;
for(;k;k>>=1,x=mul(x,x)){
if(k&1)ans=mul(ans,x);
}
return ans;
}
const int N=301;
int dp[N][N];
int upada[N][N];
int manji[N][N];
int prob[N];
int prob2[N];
vector<int> inds;
int inv[N];
int v;
vector<vector<int>> graf(N);
void solve(int tr){
vector<int> deca;
for(auto p:graf[tr]){
solve(p);
deca.pb(p);
}
inds=deca;
for(int i=0;i<sz(deca);i++)prob[i]=prob2[i]=0;
for(int k=v-1;k>=0;k--){
for(int i=0;i<sz(deca);i++)prob[i]=mul(upada[deca[i]][k],manji[deca[i]][k]);
for(int j=0;j<=sz(deca);j++)dp[sz(deca)][j]=inv[j+1];
for(int i=sz(deca)-1;i>=0;i--){
for(int j=0;j<=i;j++){
dp[i][j]=add(mul(dp[i+1][j],prob2[i]),mul(dp[i+1][j+1],prob[i]));
}
}
manji[tr][k]=dp[0][0];
for(int i=0;i<sz(deca);i++)prob2[i]=add(prob2[i],prob[i]);
}
}
int main(){
for(int i=1;i<N;i++){
inv[i]=pwrmod(i,mod-2);
}
int n;
scanf("%i",&n);
int root;
vector<int> bvals;
vector<int> bs(n);
for(int i=0;i<n;i++){
int b,r;
scanf("%i %i",&b,&r);
if(r==0){
root=i;
}
else{
r--;
graf[r].pb(i);
}
bvals.pb(b);
bs[i]=b;
}
sort(all(bvals));
bvals.erase(unique(all(bvals)),bvals.end());
v=sz(bvals);
for(int j=0;j<n;j++){
for(int i=0;i<v;i++){
int lst=0;
if(i!=0)lst=bvals[i-1];
if(lst==bs[j])break;
upada[j][i]=mul(bvals[i]-lst,pwrmod(bs[j],mod-2));
}
}
solve(root);
int ans=0;
for(int i=0;i<v;i++){
ans=add(ans,mul(upada[root][i],manji[root][i]));
}
printf("%i\n",ans);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 4324kb
input:
92 28701027 12 925341819 12 2261666 45 669601626 45 101359065 13 539500751 47 731398771 60 7638406 43 537094738 60 32248003 22 149195453 45 745987717 92 70093 92 56067991 76 5621221 47 388528561 85 385998525 12 668685623 45 664589085 92 273920428 35 495594345 60 919398 12 69316963 92 112530446 13 47...
output:
935782274
result:
wrong answer expected 276308373, found 935782274