QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#223041 | #7613. Inverse Problem | ucup-team191# | TL | 2ms | 5816kb | C++23 | 3.1kb | 2023-10-21 20:58:47 | 2023-10-21 20:58:48 |
Judging History
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 ...