QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#319090#7613. Inverse ProblemsuperguymjRE 21656ms105632kbC++203.4kb2024-02-01 20:05:252024-02-01 20:05:27

Judging History

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

  • [2024-02-01 20:05:27]
  • 评测
  • 测评结果:RE
  • 用时:21656ms
  • 内存:105632kb
  • [2024-02-01 20:05:25]
  • 提交

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

output:


result: