QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#319085 | #7613. Inverse Problem | superguymj | TL | 40811ms | 259408kb | C++20 | 3.4kb | 2024-02-01 19:34:27 | 2024-02-01 19:34:28 |
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=4;
int n;
vector <int> L[N],R[N];
vector <int> a;
void dfs(int x,int m,LL ans,int tot,vector <int> vt[])
{
if(x==m+1)
{
vt[tot].pb(ans);
return;
}
if(tot+x<=n-2)
{
dfs(x+1,m,ans,tot,vt);
dfs(x,m,ans*P(n-2,x)%mod,tot+x,vt);
}
else
dfs(m+1,m,ans,tot,vt);
}
MM(int _):n(_)
{
int m=min(K,n-3);
dfs(1,m,1,0,L);
dfs(m+1,n-2,1,0,R);
rep(i,0,n-2)
{
sort(L[i].begin(),L[i].end());
L[i].resize(unique(L[i].begin(),L[i].end())-L[i].begin());
sort(R[i].begin(),R[i].end());
R[i].resize(unique(R[i].begin(),R[i].end())-R[i].begin());
}
}
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> query(int ans)
{
ans=ans*getmi(n*(n-1),mod-2)%mod;
rep(i,0,n-2)
{
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);
while(ret.size()<n) ret.pb(0);
for(auto &i:ret) ++i;
sort(ret.begin(),ret.end());
return 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()
{
// freopen("a.in","r",stdin);
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;
if(Rs.back()==2) d[i]={1,1},++cnt;
}
flv[0]=inv[0]=1;
for(n=3; cnt<T; ++n)
{
// cout<<"TEST: "<<n<<endl;
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;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 12924kb
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: 40811ms
memory: 259408kb
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: -100
Time Limit Exceeded
input:
10 338497514 733524004 447182954 415993605 453460670 50499055 648088551 986982752 907925397 315315230