QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#319090 | #7613. Inverse Problem | superguymj | RE | 21656ms | 105632kb | C++20 | 3.4kb | 2024-02-01 20:05:25 | 2024-02-01 20:05:27 |
Judging History
answer
#include<bits/stdc++.h>
#define rep(i,x,y) for(int i=x; i<=y; ++i)
#define repd(i,x,y) for(int i=x; i>=y; --i)
#define mid ((l+r)>>1)
#define lch (rt<<1)
#define rch (rt<<1|1)
#define pb push_back
using namespace std;
typedef long long LL;
typedef __int128 i128;
typedef long double ld;
const int N=205,mod=1000000007;
int n,m,jdg;
LL flv[N],inv[N];
vector <int> a,Rs;
unordered_map <int,vector <int>> L[N][N<<1],R[N][N<<1];
int getint()
{
char ch;
int f=1;
while(!isdigit(ch=getchar())) if(ch=='-') f=-1;
int x=ch-48;
while(isdigit(ch=getchar())) x=x*10+ch-48;
return x*f;
}
LL getLL()
{
char ch;
int f=1;
while(!isdigit(ch=getchar())) if(ch=='-') f=-1;
LL x=ch-48;
while(isdigit(ch=getchar())) x=x*10+ch-48;
return x*f;
}
LL getmi(LL a,LL x)
{
LL rt=1;
while(x)
{
if(x&1) rt=rt*a%mod;
a=a*a%mod,x>>=1;
}
return rt;
}
LL P(int n,int m)
{
return n<m?0:flv[n]*inv[n-m]%mod;
}
LL invP(int n,int m)
{
return n<m?0:inv[n]*flv[n-m]%mod;
}
vector <int> operator + (vector <int> a,vector <int> b)
{
reverse(b.begin(),b.end());
for(auto i:b) a.pb(i);
return a;
}
bool count(vector <int> &a,int x)
{
auto p=lower_bound(a.begin(),a.end(),x);
if(p==a.end() || *p!=x) return 0;
return 1;
}
struct MM
{
const int K=6;
int n;
vector <int> L[N],R[N];
vector <int> a;
void init(int l,int r,vector <int> vt[])
{
vt[0].pb(1);
rep(i,l,r)
{
rep(j,0,n-2-i)
for(auto x:vt[j])
vt[j+i].pb(x*P(n-2,i)%mod);
}
rep(i,0,n-2)
{
sort(vt[i].begin(),vt[i].end());
vt[i].resize(unique(vt[i].begin(),vt[i].end())-vt[i].begin());
}
}
MM(int _):n(_)
{
int m=min(K,n-3);
init(1,m,L);
init(m+1,n-2,R);
}
vector <int> find(vector <int> vt[],int p,int ans)
{
vector <int> ret;
int x=p;
while(p)
{
if(count(vt[p-x],ans*invP(n-2,x)%mod))
ret.pb(x),ans=ans*invP(n-2,x)%mod,p-=x;
else
--x;
}
return ret;
}
vector <int> modify(vector <int> a)
{
while(a.size()<n) a.pb(0);
for(auto &i:a) ++i;
sort(a.begin(),a.end());
return a;
}
vector <int> query(int ans)
{
ans=ans*getmi(n*(n-1),mod-2)%mod;
rep(i,0,n-2)
{
if(L[i].size()<R[n-2-i].size())
for(auto x:L[i])
{
int y=ans*getmi(x,mod-2)%mod;
if(!count(R[n-2-i],y)) continue;
vector <int> ret=find(L,i,x)+find(R,n-2-i,y);
return modify(ret);
}
else
for(auto x:R[n-2-i])
{
int y=ans*getmi(x,mod-2)%mod;
if(!count(L[i],y)) continue;
vector <int> ret=find(L,i,y)+find(R,n-2-i,x);
return modify(ret);
}
}
return vector <int> ();
}
} ;
void prt(vector <int> a)
{
int n=a.size();
vector <int> leaves;
printf("%d\n",n);
if(n==1) return;
rep(i,1,n)
{
while(a[i-1]>1)
printf("%d %d\n",leaves.back(),i),--a[i-1],leaves.pop_back();
leaves.pb(i);
}
printf("%d %d\n",leaves[0],leaves[1]);
}
int main()
{
int T=getint(),cnt=0;
vector <vector <int>> d(T,vector <int> ());
rep(i,0,T-1)
{
Rs.pb(getint());
if(Rs.back()==1) d[i]={1},++cnt,Rs.back()=-1;
if(Rs.back()==2) d[i]={1,1},++cnt,Rs.back()=-1;
}
flv[0]=inv[0]=1;
for(n=3; cnt<T; ++n)
{
flv[n-2]=flv[n-3]*(n-2)%mod;
inv[n-2]=inv[n-3]*getmi(n-2,mod-2)%mod;
MM tmp=MM(n);
rep(i,0,T-1) if(Rs[i]>-1)
{
vector <int> a=tmp.query(Rs[i]);
if(!a.empty()) d[i]=a,Rs[i]=-1,++cnt;
}
}
rep(i,0,T-1) prt(d[i]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 12940kb
input:
4 2 360 1 509949433
output:
2 1 2 5 3 4 4 5 2 5 1 5 1 10 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 1 10
result:
ok OK (4 test cases)
Test #2:
score: 0
Accepted
time: 19633ms
memory: 105632kb
input:
9 185396120 468170792 837583517 696626231 338497514 762842660 800028852 928391161 733524004
output:
14 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 3 13 13 14 2 14 1 14 122 102 103 103 104 104 105 105 106 106 107 107 108 101 108 108 109 100 109 109 110 99 110 110 111 98 111 97 111 111 112 96 112 95 112 112 113 94 113 93 113 113 114 92 114 91 114 90 114 114 115 89 115 88 115 87 115 115 116 86 116 85 ...
result:
ok OK (9 test cases)
Test #3:
score: 0
Accepted
time: 21656ms
memory: 101676kb
input:
10 338497514 733524004 447182954 415993605 453460670 50499055 648088551 986982752 907925397 315315230
output:
124 102 103 103 104 104 105 105 106 106 107 107 108 108 109 109 110 110 111 111 112 112 113 101 113 113 114 100 114 99 114 114 115 98 115 97 115 96 115 95 115 115 116 94 116 93 116 92 116 91 116 90 116 116 117 89 117 88 117 87 117 86 117 85 117 84 117 117 118 83 118 82 118 81 118 80 118 79 118 78 11...
result:
ok OK (10 test cases)
Test #4:
score: -100
Runtime Error
input:
10 1 2 3 4 5 6 7 8 9 10