QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#291311 | #5567. Balanced Permutations | Crysfly# | RE | 2ms | 16232kb | C++14 | 6.7kb | 2023-12-26 11:06:26 | 2023-12-26 11:06:26 |
Judging History
answer
// what is matter? never mind.
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2")
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define int long long
#define ull unsigned long long
using namespace std;
inline int read()
{
char c=getchar();int x=0;bool f=0;
for(;!isdigit(c);c=getchar())f^=!(c^45);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
if(f)x=-x;return x;
}
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;
#define maxn 400005
#define inf 0x3f3f3f3f
const ull P[2]={9000000000000000041,9000000000000000053};
ull add(ull x,ull y,ull z){
return x+y>=z?x+y-z:x+y;
}
ull sub(ull x,ull y,ull z){
return x<y?x-y+z:x-y;
}
ull mul(ull x,ull y,ull P){
return (__int128)x*y%P;
ll s=x*y-(ll)((long double)x*y/P)*P;
if(s<0)return s+P;
return (s<P?s:s-P);
}
ull qpow(ull a,ull b,ull P){
ull c=1;
for(;b;b>>=1,a=mul(a,a,P))if(b&1)c=mul(c,a,P);
return c;
}
struct node{
ull a[2];
node(ull b=0){a[0]=(b+P[0])%P[0],a[1]=(b+P[1])%P[1];}
node(ull X,ull Y){a[0]=X,a[1]=Y;}
ull&operator [](ull b){return a[b];}
node operator +(node b){return {add(a[0],b[0],P[0]),add(a[1],b[1],P[1])};}
node operator -(node b){return {sub(a[0],b[0],P[0]),sub(a[1],b[1],P[1])};}
node operator *(node b){return {mul(a[0],b[0],P[0]),mul(a[1],b[1],P[1])};}
node inv(){return {qpow(a[0],P[0]-2,P[0]),qpow(a[1],P[1]-2,P[1])};}
node operator /(node b){return ((*this))*(b.inv());}
void operator +=(node b){(*this)=(*this)+b;}
void operator -=(node b){(*this)=(*this)-b;}
void operator *=(node b){(*this)=(*this)*b;}
void operator /=(node b){(*this)=(*this)/b;}
bool isinf(){return a[0]!=a[1];}
};
int n,k1,k2;
int f[maxn],L[maxn],R[maxn];
node g[44],C[44][44];
node fac[44],ifac[44];
int mid0[maxn],mid1[maxn];
int res[maxn];
void solve(int l,int r,int vl,int vr,int op){
// 0 : small
// 1 : large
assert(vr-vl==r-l);
if(l>r)return;
if(op==0){
int mid=l+mid0[r-l+1];
res[mid]=vr;
solve(l,mid-1,vl,vl+(mid-1-l),op);
solve(mid+1,r,vl+mid-l,vr-1,op);
}else{
int mid=l+mid1[r-l+1];
res[mid]=vr;
solve(l,mid-1,vr-1-(mid-1-l),vr-1,op);
solve(mid+1,r,vl,vr-2-(mid-1-l),op);
}
}
int m,b[42],pos[42];
bool use[42];
node dp[42][42][42];
bool vis[42][42][42];
bool ok[42][42];
int suf[42];
node dfs(int l,int r,int k){
if(!k)return 1;
if(vis[l][r][k])return dp[l][r][k];
node &res=dp[l][r][k]=0; vis[l][r][k]=1;
// cout<<"dfs "<<l<<" "<<r<<" "<<k<<"\n";
if(use[k]){
int p=pos[k];
if((p>=l)&&(!ok[l][p-1]||(p-l<L[r-l+1]||p-l>R[r-l+1])))return /*cout<<"fail "<<l<<" "<<r<<" "<<k<<"\n",*/res;
return res=dfs(max(p+1,l),r,k-1);
}
int cnt=n-r-suf[k+1];
if(cnt) res+=dfs(l,r,k-1)*cnt;
For(p,m+1,r){
// put k at p
if(p-l<L[r-l+1] || p-l>R[r-l+1])continue;
int len=r-p;
node t=dfs(l,p-1,k-1);
// cout<<"l,r,k "<<l<<" "<<r<<" "<<k<<"\n";
// cout<<"t: "<<t.a[0]<<" "<<len<<" "<<ifac[len].a[0]<<" "<<g[len].a[0]<<"\n";
res+=t*ifac[len]*g[len];
}
// cout<<"res "<<l<<" "<<r<<" "<<k<<" "<<res.a[0]<<"\n";
return res;
}
node chk(int n,int m){
// cout<<"chk "<<n<<" "<<m<<"\n";
// For(i,1,m)cout<<b[i]<<" "; cout<<" b\n";
::m=m;
memset(vis,0,sizeof vis);
For(i,1,m)pos[b[i]]=i;
suf[n+1]=0;
Rep(i,n,1) suf[i]=suf[i+1]+(!use[i]);
For(i,1,m+1)ok[i][i-1]=1;
For(len,1,m){
For(i,1,m-len+1){
int j=i+len-1,p=i;
For(k,i,j)if(b[k]>b[p])p=k;
ok[i][j]=(ok[i][p-1]&&ok[p+1][j]&&(p-i>=L[len]&&p-i<=R[len]));
}
}
node res=dfs(1,n,n);
// cout<<res.a[0]<<" "<<res.isinf()<<"\n";
return res;
}
void solve_small(int k){
if(n<=30){
if(!g[n].isinf() && k>g[n].a[0]){
puts("-1");
return;
}
}
int n=::n;
int lst=1;
int nowl=1,nowr=n;
while(n){
// cout<<"n: "<<n<<" "<<lst<<" "<<nowl<<" "<<nowr<<"\n";
int pos=mid0[n];
bool ok=0;
if(g[n-1-pos].isinf() || g[n-1-pos].a[0]>=k) ok=1;
if(ok){
// cout<<"pos "<<pos<<"\n";
res[lst+pos]=nowr;
solve(lst,lst+pos-1,nowl,nowl+pos-1,0);
// For(_,1,::n)cout<<res[_]<<" "; cout<<"\n";
n-=pos+1;
lst+=pos+1;
nowl+=pos;
nowr-=1;
continue;
}
assert(n<=40);
For(i,1,n)use[i]=0;
For(i,1,n){
bool qwq=0;
For(j,1,n) if(!use[j]) {
b[i]=j; use[j]=1;
node t=chk(n,i);
if(t.isinf() || t.a[0]>=k){
use[j]=qwq=1;
break;
}
k-=t.a[0];
use[j]=0;
}
assert(qwq);
}
For(i,1,n) res[lst+i-1]=nowl+b[i]-1;
break;
}
For(i,1,::n) cout<<res[i]<<" "; cout<<"\n";
}
void solve_large(int k){
if(n<=30){
if(!g[n].isinf() && k>g[n].a[0]){
puts("-1");
return;
}
}
int n=::n;
int lst=1;
int nowl=1,nowr=n;
while(n){
// cout<<"n: "<<n<<" "<<lst<<" "<<nowl<<" "<<nowr<<"\n";
int pos=mid1[n];
bool ok=0;
if(g[n-1-pos].isinf() || g[n-1-pos].a[0]>=k) ok=1;
if(ok){
// cout<<"pos "<<pos<<"\n";
res[lst+pos]=nowr;
solve(lst,lst+pos-1,nowr-pos,nowr-1,0);
// For(_,1,::n)cout<<res[_]<<" "; cout<<"\n";
n-=pos+1;
lst+=pos+1;
nowr-=pos+1;
continue;
}
assert(n<=40);
For(i,1,n)use[i]=0;
For(i,1,n){
bool qwq=0;
Rep(j,n,1) if(!use[j]) {
b[i]=j; use[j]=1;
node t=chk(n,i);
if(t.isinf() || t.a[0]>=k){
use[j]=qwq=1;
break;
}
k-=t.a[0];
use[j]=0;
}
assert(qwq);
}
For(i,1,n) res[lst+i-1]=nowl+b[i]-1;
break;
}
For(i,1,::n) cout<<res[i]<<" "; cout<<"\n";
}
signed main()
{
f[1]=1;
L[1]=R[1]=0;
g[1]=g[0]=1;
C[0][0]=1;
For(i,1,40){
C[i][0]=1;
For(j,1,i) C[i][j]=C[i-1][j]+C[i-1][j-1];
}
fac[0]=ifac[0]=1;
For(i,1,40)fac[i]=fac[i-1]*i,ifac[i]=ifac[i-1]/i;
For(i,2,10000){
f[i]=f[(i-1)/2]+f[i-1-(i-1)/2]+i;
int l=0,r=(i-1)/2,pos=(i-1)/2;
while(l<=r){
int mid=l+r>>1;
if(f[mid]+f[i-1-mid]+i==f[i])pos=mid,r=mid-1;
else l=mid+1;
}
L[i]=pos,R[i]=i-1-pos;
// cout<<i<<" "<<f[i]<<" "<<::l[i]<<" "<<::r[i]<<"\n";
if(i<=40){
For(j,L[i],R[i])
g[i]+=C[i-1][j]*g[j]*g[i-1-j];
// cout<<"i: "<<i<<" "<<L[i]<<" "<<R[i]<<" "<<g[i].a[0]<<" "<<g[i].a[1]<<"\n";
}
}
mid0[1]=0;
For(i,2,10000){
int k=0,up=i/2;
while((1<<(k+1))<=up) ++k;
mid0[i]=max((1ll<<k),L[i]);
mid1[i]=max((1ll<<k)-1,L[i]);
// if(i<=500)cout<<"imid: "<<i<<" "<<mid0[i]<<" "<<mid1[i]<<"\n";
}
n=read(),k1=read(),k2=read();
solve_small(k1);
solve_large(k2);
return 0;
}
/*
4
1 3 2 4
3 4 1 2
*/
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 15016kb
input:
3 1 2
output:
1 3 2 1 3 2
result:
ok 6 numbers
Test #2:
score: 0
Accepted
time: 0ms
memory: 16232kb
input:
4 9 13
output:
3 1 4 2 -1
result:
ok 5 number(s): "3 1 4 2 -1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 15016kb
input:
4 20 7
output:
-1 2 3 4 1
result:
ok 5 number(s): "-1 2 3 4 1"
Test #4:
score: -100
Runtime Error
input:
99500 1000000000000000000 1000000000000000000