QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#223041#7613. Inverse Problemucup-team191#TL 2ms5816kbC++233.1kb2023-10-21 20:58:472023-10-21 20:58:48

Judging History

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

  • [2023-10-21 20:58:48]
  • 评测
  • 测评结果:TL
  • 用时:2ms
  • 内存:5816kb
  • [2023-10-21 20:58:47]
  • 提交

answer

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using vi=vector<int>;
using vl=vector<ll>;
using ld=long double;
#define all(a) begin(a),end(a)
#define pb push_back

const int N=310,MOD=1e9+7;
const char en='\n';
const ll LLINF=1ll<<60;

int mul(int a,int b)
{
	return a*1ll*b%MOD;
}

int pot(int n,int k)
{
	if (k==0) return 1;
	int r=pot(n,k/2);
	r=mul(r,r);
	if (k%2) r=mul(r,n);
	return r;
}

int inv(int x)
{
	return pot(x,MOD-2);
}

int t,rrem,rem,n,ms,efn;
vi mog;

vi cur;
int cuu;
vector<pii> svp[N][N];
vector<vi> zar[N];
bool bil;
vi ans;

void bact(int s,int la)
{
	if (mul(cuu,mog[efn-s])==rem)
	{
		ans=cur;
		ans.pb(efn-s);
		//cout<<s<<en;
		//for (auto x: ans) cout<<x<<' ';
		//cout<<en;
		return;
	}
	if (s>=efn/3)
	{
		if (!bil)
		{
			auto it=lower_bound(all(zar[s]),cur);
			if (it==zar[s].end() || *it!=cur)
			{
				svp[efn][s].pb({cuu,zar[s].size()});
				zar[s].pb(cur);
			}
			else svp[efn][s].pb({cuu,it-zar[s].begin()});
		}
		else return;
	}
	if (s<=(efn-1)/2) for (int ne=la;ne>=1;--ne) if (s+ne<=ms)
	{
		cur.pb(ne);
		int scuu=cuu;
		cuu=mul(cuu,mog[ne]);
		bact(s+ne,ne);
		cuu=scuu;
		cur.pop_back();
	}
}

void out()
{
	cout<<n<<endl;
	cout<<1<<' '<<2<<endl;
	int cu=2;
	for (auto x: ans)
	{
		for (int i=1;i<=x;++i) cout<<cu<<' '<<cu+i<<endl;
		cu+=x;
	}
}

bool pok()
{
	rem=mul(rrem,mul(inv(n),inv(n-1)));
	mog.clear();
	mog.pb(1);
	mog.pb(n-2);
	while (mog.back()>1) mog.pb(mog.back()-1);
	for (int i=1;i<(int)mog.size();++i) mog[i]=mul(mog[i],mog[i-1]);
	//cout<<n<<' '<<rem<<endl;
	//for (auto x: mog) cout<<x<<' ';
	//cout<<endl<<endl;
	ans.clear();
	efn=n-2;
	ms=(efn*2+2)/3;
	cur.clear();
	cuu=1;
	//cout<<n<<endl;
	bil=svp[efn][efn/3].size()>0;
	bact(0,efn);
	int s1=0,s2=0;
	if (!bil) for (int i=efn/3;i<=ms;++i)
	{
		if (i<=efn/2) s1+=svp[efn][i].size();
		else s2+=svp[efn][i].size();
		sort(all(svp[efn][i]));
	}
	//cout<<n<<' '<<s1<<' '<<s2<<endl;
	if (ans.size())
	{
		out();
		return 1;
	}
	int jed=0;
	for (int sz=(efn+1)/2;sz<=ms;++sz)
	{
		vector<pii> qs;
		for (int i=0;i<(int)svp[efn][sz].size();++i)
		{
			int potr=mul(rem,inv(svp[efn][sz][i].x));
			qs.pb({potr,i});
		}
		sort(all(qs));
		int pos=0;
		for (auto x: qs)
		{
			while (pos<(int)svp[efn][efn-sz].size() && svp[efn][efn-sz][pos].x<x.x) ++pos;
			if (pos==(int)svp[efn][efn-sz].size() || svp[efn][efn-sz][pos].x!=x.x) continue;
			//cout<<sz<<en;
			//for (auto x: svp[sz][i].y) cout<<x<<' ';
			//cout<<en;
			//cout<<efn-sz<<en;
			//for (auto x: it->y) cout<<x<<' ';
			//cout<<en;
			ans=zar[sz][svp[efn][sz][x.y].y];
			for (auto x: zar[efn-sz][svp[efn][efn-sz][pos].y]) ans.pb(x);
			out();
			return 1;
		}
	}
	//cout<<jed<<endl;
	return 0;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin>>t;
	while (t--)
	{
		cin>>rrem;
		if (rrem==1)
		{
			cout<<1<<en;
			continue;
		}
		if (rrem==2)
		{
			cout<<2<<en<<"1 2"<<en;
			continue;
		}
		for (n=3;;++n)
		{
			if (pok()) break;
		}
	}
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 5816kb

input:

4
2
360
1
509949433

output:

2
1 2
5
1 2
2 3
3 4
3 5
1
10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10

result:

ok OK (4 test cases)

Test #2:

score: -100
Time Limit Exceeded

input:

9
185396120
468170792
837583517
696626231
338497514
762842660
800028852
928391161
733524004

output:

14
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
8 10
10 11
10 12
12 13
13 14
122
1 2
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 12
2 13
2 14
2 15
2 16
2 17
2 18
2 19
2 20
2 21
2 22
2 23
2 24
2 25
2 26
2 27
2 28
2 29
2 30
2 31
31 32
31 33
31 34
31 35
31 36
31 37
31 38
31 39
31 40
31 41
31 42
42 43
42 44
42 45
45 46
...

result: