QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#319085#7613. Inverse ProblemsuperguymjTL 40811ms259408kbC++203.4kb2024-02-01 19:34:272024-02-01 19:34:28

Judging History

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

  • [2024-02-01 19:34:28]
  • 评测
  • 测评结果:TL
  • 用时:40811ms
  • 内存:259408kb
  • [2024-02-01 19:34:27]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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

output:


result: