QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#319096 | #7613. Inverse Problem | superguymj | AC ✓ | 22058ms | 103780kb | C++20 | 3.4kb | 2024-02-01 20:18:01 | 2024-02-01 20:18:03 |
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(p-x>=0 && 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: 13000kb
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: 19917ms
memory: 103780kb
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: 22058ms
memory: 101744kb
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: 0
Accepted
time: 5365ms
memory: 38572kb
input:
10 1 2 3 4 5 6 7 8 9 10
output:
1 2 1 2 102 87 88 88 89 89 90 90 91 86 91 91 92 85 92 92 93 84 93 93 94 83 94 94 95 82 95 95 96 81 96 80 96 79 96 78 96 77 96 96 97 76 97 75 97 74 97 73 97 72 97 71 97 70 97 97 98 69 98 68 98 67 98 66 98 65 98 64 98 63 98 62 98 98 99 61 99 60 99 59 99 58 99 57 99 56 99 55 99 54 99 53 99 99 100 52 10...
result:
ok OK (10 test cases)
Test #5:
score: 0
Accepted
time: 2035ms
memory: 23684kb
input:
10 269199917 392009324 753889928 751355133 472639410 132096559 331333826 40414701 72847302 475706026
output:
55 54 55 53 55 52 55 51 55 50 55 49 55 48 55 47 55 46 55 45 55 44 55 43 55 42 55 41 55 40 55 39 55 38 55 37 55 36 55 35 55 34 55 33 55 32 55 31 55 30 55 29 55 28 55 27 55 26 55 25 55 24 55 23 55 22 55 21 55 20 55 19 55 18 55 17 55 16 55 15 55 14 55 13 55 12 55 11 55 10 55 9 55 8 55 7 55 6 55 5 55 4 ...
result:
ok OK (10 test cases)
Extra Test:
score: 0
Extra Test Passed