网站空间购买价格,中山移动网站建设多少钱,万江网站建设,重庆网站模板建站公司正题 题目大意
求n个数的全排列的第k个。 解题思路
首先康拓逆展开 ∑iinxi(n−i)!\sum^{in}_i x_i(n-i)!∑iinxi(n−i)! 求每个时候第xxx大的数 然后因为n(n−1)!n!n(n-1)!n!n(n−1)!n! so我们可以直接用余数 这是n3n3n3时是序列#xff0c;我们可以发现我…正题 题目大意
求n个数的全排列的第k个。 解题思路
首先康拓逆展开 ∑iilt;nxi(n−i)!\sum^{ilt;n}_i x_i(n-i)!∑iinxi(n−i)! 求每个时候第xxx大的数 然后因为n(n−1)!n!n(n-1)!n!n(n−1)!n! so我们可以直接用余数 这是n3n3n3时是序列我们可以发现我们需要求第xix_ixi个。这时候我们可以用二分加树状数组来log2log^2log2的求答案。 之后我们又会发现 ∑iilt;nxi(n−i)!\sum^{ilt;n}_i x_i(n-i)!∑iinxi(n−i)! 这个直接计算时间复杂度是n2log2nwn^2\ log^2n\ wn2 log2n w(w是高进度位数)。 这时我们引入: x%yz/zx/z%yx\%yz/zx/z\%yx%yz/zx/z%y 证明: 这时候我们可以枚举1∼n1\sim n1∼n然后每次kmodik\ mod\ ik mod i这时候的余数就是上面式子n−i1n-i1n−i1次的余数。 code
#includeiostream
#includecstring
#define lobit(x) x-x
#define N 100010
#define ll long long
using namespace std;
ll a[N*2],n,t[N],l,mo[N];
char k[N*2];
void change(ll x,ll num)//改变
{while(xn){t[x]num;xlobit(x);}
}
ll ask(ll x)//询问
{ll sum0;while(x){sumt[x];x-lobit(x);}return sum;
}
void read()//输入——高精度
{scanf(%s,k);lstrlen(k)-1;ll L0;for(ll il;i0;i--) L((l-i)%13)0,mo[i]L-1;//压行之后的位置for(ll i0;il;i) a[mo[i]]a[mo[i]]*10k[i]-48;//求值a[0]--;for(ll i0;il;i) if(a[i]0) a[i1]--,a[i](1e13);//要先-1lL-1;
}
ll div(ll x)//高精除
{ ll g0;for (ll il;i0;i--){ll s;sg*(1e13)a[i];a[i]s/x;gs%x;}while(!a[l]) l--;return g;
}
int main()
{scanf(%lld,n);read();for(ll i1;in;i)mo[n-i1]div(i);//计算余数for(ll i1;in;i) {ll ans0;for(ll l1,rn;lr;) {ll m(lr)/2;ll s0,xm;sx-ask(x);if(smo[i]) lm1;else ansm,rm-1;}//二分位置ll xans;change(x,1);//去掉这个数printf(%lld ,ans);}return 0;
}
