QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#227639#7613. Inverse Problemucup-team1004AC ✓40022ms356168kbC++144.1kb2023-10-27 20:24:582023-10-27 20:24:59

Judging History

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

  • [2023-10-27 20:24:59]
  • 评测
  • 测评结果:AC
  • 用时:40022ms
  • 内存:356168kb
  • [2023-10-27 20:24:58]
  • 提交

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

详细

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