QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#319096#7613. Inverse ProblemsuperguymjAC ✓22058ms103780kbC++203.4kb2024-02-01 20:18:012024-02-01 20:18:03

Judging History

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

  • [2024-02-01 20:18:03]
  • 评测
  • 测评结果:AC
  • 用时:22058ms
  • 内存:103780kb
  • [2024-02-01 20:18:01]
  • 提交

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

詳細信息

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