QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#227639 | #7613. Inverse Problem | ucup-team1004 | AC ✓ | 40022ms | 356168kb | C++14 | 4.1kb | 2023-10-27 20:24:58 | 2023-10-27 20:24:59 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
template<typename T>
ostream& operator << (ostream &out,const vector<T> &x){
if(x.empty())return out<<"[]";
out<<'['<<x[0];
for(int i=1,len=x.size();i<len;i++)out<<','<<x[i];
return out<<']';
}
template<typename T1,typename T2,typename T3>
ostream& operator << (ostream &out,const tuple<T1,T2,T3> &x){
return out<<'('<<get<0>(x)<<','<<get<1>(x)<<','<<get<2>(x)<<')';
}
template<typename T>
vector<T> ary(const T *a,int l,int r){
return vector<T>{a+l,a+1+r};
}
template<typename T>
void debug(T x){
cerr<<x<<endl;
}
template<typename T,typename ... S>
void debug(T x,S...y){
cerr<<x<<' ',debug(y...);
}
const int N=150,M=15,mod=1e9+7;
int n,m,cnt,goal[N];
pair<int,vector<int> >ans[N];
int fac[N],ifac[N],inv[N];
ll qpow(ll x,ll y=mod-2){
ll ans=1;
for(;y;(x*=x)%=mod,y>>=1)if(y&1)(ans*=x)%=mod;
return ans;
}
ll f[N][N][N],g[N][N][N],F[N][N],G[N][N];
void init(int n=N-1){
for(int i=inv[1]=fac[0]=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%mod;
for(int i=2;i<=n;i++)inv[i]=1ll*inv[mod%i]*(mod-mod/i)%mod;
for(int i=ifac[0]=1;i<=n;i++)ifac[i]=1ll*ifac[i-1]*inv[i]%mod;
for(int lim=1;lim<=n;lim++){
f[lim][0][0]=1;
for(int r=1;r<=lim;r++){
memcpy(f[lim][r],f[lim][r-1],sizeof f[lim][r]);
for(int j=r;j<=lim;j++){
f[lim][r][j]+=f[lim][r][j-r];
}
F[lim][r]=accumulate(f[lim][r],f[lim][r]+1+lim,0ll);
}
}
for(int lim=1;lim<=n;lim++){
g[lim][lim+1][0]=1;
for(int r=lim;r>=1;r--){
memcpy(g[lim][r],g[lim][r+1],sizeof g[lim][r]);
for(int j=r;j<=lim;j++){
g[lim][r][j]+=g[lim][r][j-r];
}
G[lim][r]=accumulate(g[lim][r],g[lim][r]+1+lim,0ll);
}
}
// for(int lim=1;lim<=n;lim++){
// debug("F",ary(F[lim],1,lim));
// debug("G",ary(G[lim],1,lim));
// }
}
int P(int n,int m){
if(0>m||m>n)return 0;
return 1ll*fac[n]*ifac[n-m]%mod;
}
int iP(int n,int m){
if(0>m||m>n)return 0;
return 1ll*ifac[n]*fac[n-m]%mod;
}
int val[N],ival[N];
vector<pair<int,vector<int> > >S,T;
vector<int>now;
void dfs1(int n,int l,int r,int sum,int mul){
// if(sum<n&&sum+l>n)return;
if(sum==n)S.push_back({mul,now});
for(int i=l;i<=r&&sum+i<=n;i++){
now.push_back(i);
dfs1(n,i,r,sum+i,1ll*mul*ival[i]%mod);
now.pop_back();
}
}
void dfs2(int n,int l,int r,int sum,int mul){
if(sum==n)T.push_back({mul,now});
for(int i=l;i<=r&&sum+i<=n;i++){
now.push_back(i);
dfs2(n,i,r,sum+i,1ll*mul*val[i]%mod);
now.pop_back();
}
}
bitset<mod>vis;
int t3;
void solve(int n){
int B=0;
ll mn=1e18;
for(int i=1;i<n;i++){
ll now=max(F[n][i]*cnt,G[n][i+1]);
if(now<mn)mn=now,B=i;
}
for(int i=1;i<=n;i++)val[i]=P(n,i),ival[i]=iP(n,i);
// debug(ary(val,1,n),ary(ival,1,n));
// sort(S.begin(),S.end());
// sort(T.begin(),T.end());
// debug(S),debug(T);
for(int l=0;l<=n;l++){
int r=n-l;
S.clear(),T.clear();
dfs1(l,1,B,0,1);
dfs2(r,B+1,n,0,1);
for(auto &Tx:T){
vis[Tx.first]=1;
}
for(int i=1;i<=m;i++)if(!ans[i].first){
int x=1ll*goal[i]*inv[n+1]%mod*inv[n+2]%mod;
for(auto &Sx:S){
int mul=1ll*x*Sx.first%mod;
if(!vis[mul])continue;
// debug("???");
for(auto &Tx:T){
if(Tx.first!=mul)continue;
ans[i].first=n+2;
vector<int>res(Sx.second);
for(int x:Tx.second)res.push_back(x);
res[0]++;
for(;res.size()<n+2;res.push_back(0));
ans[i].second=res,cnt--;
debug("ok",i,ans[i].first,ans[i].second);
break;
}
break;
}
}
for(auto &Tx:T){
vis[Tx.first]=0;
}
}
debug(n);
}
int main(){
cin>>m,init();
for(int i=1;i<=m;i++)cin>>goal[i];
cnt=m;
for(int i=1;i<=m;i++){
if(goal[i]==1)cnt--,ans[i]={1,{0}};
else if(goal[i]==2)cnt--,ans[i]={2,{1,0}};
if(ans[i].first){
debug("ok",i,ans[i].first,ans[i].second);
}
}
for(n=3;cnt;n++)solve(n-2);
for(int i=1;i<=m;i++){
// debug(ans[i].first,ans[i].second);
int n=ans[i].first;
printf("%d\n",n);
for(int j=0,x=1;j<n;j++){
for(;ans[i].second[j]--;){
printf("%d %d\n",j+1,x+++1);
}
}
}
debug(1.0*clock()/CLOCKS_PER_SEC);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 6ms
memory: 56820kb
input:
4 2 360 1 509949433
output:
2 1 2 5 1 2 1 3 2 4 2 5 1 10 1 2 1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10
result:
ok OK (4 test cases)
Test #2:
score: 0
Accepted
time: 32416ms
memory: 345456kb
input:
9 185396120 468170792 837583517 696626231 338497514 762842660 800028852 928391161 733524004
output:
14 1 2 1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 9 12 10 13 10 14 122 1 2 1 3 2 4 3 5 4 6 5 7 6 8 6 9 7 10 7 11 8 12 8 13 9 14 9 15 9 16 10 17 10 18 10 19 11 20 11 21 11 22 12 23 12 24 12 25 12 26 13 27 13 28 13 29 13 30 14 31 14 32 14 33 14 34 14 35 15 36 15 37 15 38 15 39 15 40 15 41 15 42 16 43 16 44...
result:
ok OK (9 test cases)
Test #3:
score: 0
Accepted
time: 40022ms
memory: 356168kb
input:
10 338497514 733524004 447182954 415993605 453460670 50499055 648088551 986982752 907925397 315315230
output:
124 1 2 1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 10 12 11 13 11 14 12 15 12 16 12 17 13 18 13 19 13 20 13 21 13 22 14 23 14 24 14 25 14 26 14 27 14 28 15 29 15 30 15 31 15 32 15 33 15 34 15 35 16 36 16 37 16 38 16 39 16 40 16 41 16 42 17 43 17 44 17 45 17 46 17 47 17 48 17 49 18 50 18 51 18 52 18 53 18...
result:
ok OK (10 test cases)
Test #4:
score: 0
Accepted
time: 6044ms
memory: 200384kb
input:
10 1 2 3 4 5 6 7 8 9 10
output:
1 2 1 2 102 1 2 1 3 2 4 3 5 4 6 4 7 5 8 5 9 6 10 6 11 7 12 7 13 8 14 8 15 9 16 9 17 9 18 9 19 9 20 9 21 10 22 10 23 10 24 10 25 10 26 10 27 10 28 10 29 11 30 11 31 11 32 11 33 11 34 11 35 11 36 11 37 11 38 12 39 12 40 12 41 12 42 12 43 12 44 12 45 12 46 12 47 12 48 13 49 13 50 13 51 13 52 13 53 13 5...
result:
ok OK (10 test cases)
Test #5:
score: 0
Accepted
time: 1787ms
memory: 187984kb
input:
10 269199917 392009324 753889928 751355133 472639410 132096559 331333826 40414701 72847302 475706026
output:
55 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 1 24 1 25 1 26 1 27 1 28 1 29 1 30 1 31 1 32 1 33 1 34 1 35 1 36 1 37 1 38 1 39 1 40 1 41 1 42 1 43 1 44 1 45 1 46 1 47 1 48 1 49 1 50 1 51 1 52 1 53 1 54 1 55 84 1 2 1 3 2 4 3 5 4 6 5 7 6 8 7 9 ...
result:
ok OK (10 test cases)
Extra Test:
score: 0
Extra Test Passed