QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#232518 | #7613. Inverse Problem | AFewSuns | WA | 1ms | 3604kb | C++14 | 3.5kb | 2023-10-30 15:52:07 | 2023-10-30 15:52:09 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
namespace my_std{
#define ll long long
#define bl bool
ll my_pow(ll a,ll b,ll mod){
ll res=1;
if(!b) return 1;
while(b){
if(b&1) res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res;
}
ll qpow(ll a,ll b){
ll res=1;
if(!b) return 1;
while(b){
if(b&1) res*=a;
a*=a;
b>>=1;
}
return res;
}
#define db double
#define pf printf
#define pc putchar
#define fr(i,x,y) for(register ll i=(x);i<=(y);i++)
#define pfr(i,x,y) for(register ll i=(x);i>=(y);i--)
#define go(u) for(ll i=head[u];i;i=e[i].nxt)
#define enter pc('\n')
#define space pc(' ')
#define fir first
#define sec second
#define MP make_pair
#define il inline
#define inf 8e18
#define random(x) rand()*rand()%(x)
#define inv(a,mod) my_pow((a),(mod-2),(mod))
il ll read(){
ll sum=0,f=1;
char ch=0;
while(!isdigit(ch)){
if(ch=='-') f=-1;
ch=getchar();
}
while(isdigit(ch)){
sum=sum*10+(ch^48);
ch=getchar();
}
return sum*f;
}
il void write(ll x){
if(x<0){
x=-x;
pc('-');
}
if(x>9) write(x/10);
pc(x%10+'0');
}
il void writeln(ll x){
write(x);
enter;
}
il void writesp(ll x){
write(x);
space;
}
}
using namespace my_std;
#define mod 1000000007
vector<pair<ll,ll> > ans[11];
vector<ll> vec1[220],vec2[220];
ll q,n=2,a[11],f[220],ff[220],b[220],cntb,c[220],cntc,d[220];
void dfs1(ll now,ll sum,ll mul){
vec1[sum].push_back(mul);
fr(i,now,min(5ll,n-2-sum)) dfs1(i,sum+i,mul*f[i]%mod);
}
void dfs2(ll now,ll sum,ll mul){
vec2[sum].push_back(mul);
fr(i,now,n-2-sum) dfs2(i,sum+i,mul*ff[i]%mod);
}
bl dfs3(ll now,ll sum,ll mul,ll nsum,ll nmul){
if(nsum==sum&&nmul==mul) return 1;
if(sum>=nsum) return 0;
fr(i,now,min(5ll,n-2-sum)){
b[++cntb]=i;
if(dfs3(i,sum+i,mul*f[i]%mod,nsum,nmul)) return 1;
cntb--;
}
return 0;
}
bl dfs4(ll now,ll sum,ll mul,ll nsum,ll nmul){
if(nsum==sum&&nmul==mul) return 1;
if(sum>=nsum) return 0;
fr(i,now,n-2-sum){
c[++cntc]=i;
if(dfs4(i,sum+i,mul*ff[i]%mod,nsum,nmul)) return 1;
cntc--;
}
return 0;
}
il void solve(){
pf("%lld start\n",n);
ll tmp=1;
fr(i,0,n-2){
f[i]=tmp;
tmp=tmp*(n-2-i)%mod;
}
fr(i,0,n-2) ff[i]=inv(f[i],mod);
dfs1(1,0,1);
dfs2(6,0,1);
fr(i,0,n-2) sort(vec2[i].begin(),vec2[i].end());
fr(i,1,q){
if(!ans[i].empty()) continue;
tmp=n*(n-1)%mod*inv(a[i],mod)%mod;
fr(j,0,n-2){
ll res1=-1,res2=-1;
fr(k,0,(ll)vec1[j].size()-1){
ll now=vec1[j][k]*tmp%mod,pos=lower_bound(vec2[n-2-j].begin(),vec2[n-2-j].end(),now)-vec2[n-2-j].begin();
if(pos<(ll)vec2[n-2-j].size()&&vec2[n-2-j][pos]==now){
res1=vec1[j][k];
res2=now;
break;
}
}
if(res1==-1) continue;
pf("query #%lld done\n",i);
cntb=cntc=0;
dfs3(1,0,1,j,res1);
dfs4(6,0,1,n-2-j,res2);
fr(k,1,n) d[k]=0;
fr(k,1,cntb) d[k]=b[k];
fr(k,1,cntc) d[cntb+k]=c[k];
ll now=1;
fr(k,1,n){
while(d[k]--) ans[i].push_back(MP(k,++now));
if(k==1) ans[i].push_back(MP(k,++now));
}
break;
}
}
fr(i,0,n-2) vec1[i].clear();
fr(i,0,n-2) vec2[i].clear();
pf("%lld end\n",n);
}
int main(){
q=read();
fr(i,1,q){
a[i]=read();
if(a[i]==1) ans[i].push_back(MP(0,0));
}
while(1){
bl ck=0;
fr(i,1,q) if(ans[i].empty()) ck=1;
if(!ck) break;
solve();
n++;
}
fr(i,1,q){
if(!ans[i][0].fir) writeln(1);
else{
writeln((ll)ans[i].size()+1);
fr(j,0,(ll)ans[i].size()-1) pf("%lld %lld\n",ans[i][j].fir,ans[i][j].sec);
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3604kb
input:
4 2 360 1 509949433
output:
2 start query #1 done 2 end 3 start 3 end 4 start 4 end 5 start query #2 done 5 end 6 start 6 end 7 start 7 end 8 start 8 end 9 start 9 end 10 start query #4 done 10 end 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:
wrong output format Expected integer, but "start" found