T1 [TJOI2019] 甲苯先生的滚榜
平衡树裸题,随便一种平衡树应该都可以.但是要注意常数问题,不要以为 (10s) 的时限很松...
#include <cstdio>
#include <cstring>
typedef long long ll;
typedef unsigned int ui;
inline int rd(){
int x=0,p=1;
char a=getchar();
while((a<48||a>57)&&a!='-')a=getchar();
if(a=='-')p=-p,a=getchar();
while(a>47&&a<58)x=(x<<1)+(x<<3)+(a&15),a=getchar();
return x*p;
}
inline ui randNum(ui &seed, ui last,const ui m){
seed=seed*17+last;
return seed%m+1;
}
const int N=100002;
ui seed,lst=7;
int T,n,q;
int root,Size,ft[N],cnt[N],son[N][2],vala[N],valb[N],size[N];
int ac[N],ti[N];
inline void init(){
memset(ac,0,sizeof ac);
memset(ti,0,sizeof ti);
memset(ft,0,sizeof ft);
memset(son,0,sizeof son);
memset(cnt,0,sizeof cnt);
memset(vala,0,sizeof vala);
memset(valb,0,sizeof valb);
memset(size,0,sizeof size);
root=0,Size=0;
}
inline void pushup(int x){
size[x]=size[son[x][0]]+size[son[x][1]]+cnt[x];
}
inline int get(int x){
return x==son[ft[x]][1];
}
inline void clear(int x){
son[x][0]=son[x][1]=ft[x]=cnt[x]=vala[x]=valb[x]=size[x]=0;
}
inline void rotate(int x){
int f=ft[x],ff=ft[f],d=get(x);
son[f][d]=son[x][d^1],ft[son[x][d^1]]=f;
son[x][d^1]=f,ft[ff]=x;
ft[x]=ff;
if(ff)son[ff][get(f)]=x;
pushup(f),pushup(x);
}
inline void splay(int x,int g=0){
while(ft[x]!=g){
int f=ft[x],ff=ft[f];
if(ff!=g) get(x)==get(f)?rotate(f):rotate(x);
rotate(x);
}
if(!g) root=x;
}
inline void insert(int a,int b){
if(!root){
vala[++Size]=a,valb[Size]=b;
root=Size,cnt[Size]++;
pushup(root);
return;
}
int now=root,f=0;
while(1){
if(vala[now]==a&&valb[now]==b){
cnt[now]++,pushup(now),splay(now);
break;
}
f=now;
if(a<vala[now]||(a==vala[now]&&b>valb[now])) now=son[now][1];
else now=son[now][0];
if(!now){
vala[++Size]=a,valb[Size]=b;
cnt[Size]++;
ft[Size]=f,son[f][a<vala[f]||(a==vala[f]&&b>valb[f])]=Size;
pushup(f),pushup(Size);
splay(Size);
break;
}
}
}
inline int rank(int a,int b){
int ans=0,now=root;
while(1){
if(a>vala[now]||(a==vala[now]&&b<valb[now])) now=son[now][0];
else{
ans+=size[son[now][0]];
if(a==vala[now]&&b==valb[now]){
splay(now);
return ans+1;
}
ans+=cnt[now],now=son[now][1];
}
}
}
inline int pre(){
int now=son[root][0];
while(son[now][1]) now=son[now][1];
return now;
}
inline void del(int a,int b){
rank(a,b);
if(cnt[root]>1){
cnt[root]--,pushup(root);
return;
}
if(!son[root][0]&&!son[root][1]){
clear(root),root=0;
return;
}
if(!son[root][0]){
int now=root;
root=son[now][1];
ft[root]=0;
clear(now);
return;
}
if(!son[root][1]){
int now=root;
root=son[now][0];
ft[root]=0;
clear(now);
return;
}
int x=pre(),now=root;
splay(x);
ft[son[now][1]]=x;
son[x][1]=son[now][1];
clear(now);
pushup(root);
}
int main(){
freopen("roll.in","r",stdin);
freopen("roll.out","w",stdout);
T=rd();
while(T--){
init();
n=rd(),q=rd(),seed=rd();
while(q--){
ui ria=randNum(seed,lst,n);
ui rib=randNum(seed,lst,n);
if(ac[ria]) del(ac[ria],ti[ria]);
ac[ria]++,ti[ria]+=rib;
insert(ac[ria],ti[ria]);
lst=rank(ac[ria],ti[ria])-1;
printf("%d
",lst);
}
}
return 0;
}
T2 [SDOI2016]排列计数
设 (f_{i}) 为 (n) 个数任意一个数都不在对应位置上的排列方案数,则答案为 (dbinom{n}{m} * f_{n-m}).
显然 (f_{1}=0 , f_{2}=1).设 (n) 被放在了第 (k) 个位置,则若 (k) 在第 (n) 位,则已确定两个数,相当于 (f_{n-2});当 (k) 不在第 (n) 位时只能确定一个,相当于 (f_{n-1}). 由于 (k) 有 (n-1) 种取值,所以综合以上公式得到:
[f_{i}=(n-1)*(f_{i-1}+f_{i-2})
]
再配合组合数和逆元即可求解.
#include <cstdio>
#include <algorithm>
typedef long long ll;
inline int rd(){
int x=0,p=1;
char a=getchar();
while((a<48||a>57)&&a!='-')a=getchar();
if(a=='-')p=-p,a=getchar();
while(a>47&&a<58)x=(x<<1)+(x<<3)+(a&15),a=getchar();
return x*p;
}
const int N=1000002,S=1000000;
const ll mod=1e9+7;
int T,n,m;
ll fac[N],inv[N],f[N];
ll ans=0;
inline ll fpow(ll b,ll p=mod-2){
ll ans=1,tmp=b;
while(p){
if(p&1)ans=ans*tmp%mod;
tmp=tmp*tmp%mod;
p>>=1;
}
return ans;
}
inline ll C(int n,int m){
return fac[n]*inv[n-m]%mod*inv[m]%mod;
}
int main(){
freopen("permutation.in","r",stdin);
freopen("permutation.in","w",stdout);
fac[0]=1;
for(int i=1;i<=S;i++)fac[i]=fac[i-1]*i%mod;
inv[S]=fpow(fac[S]);
for(int i=S-1;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;
f[1]=0,f[2]=1;
for(int i=3;i<=S;i++)f[i]=(i-1)*(f[i-1]+f[i-2])%mod;
T=rd();
while(T--){
n=rd(),m=rd();
if(n==m)puts("1");
else printf("%lld
",C(n,m)*f[n-m]%mod);
}
return 0;
}
T3 [CQOI2007]余数求和
[sumlimits_{i=1}^{n}k mod i
]
[=n*k - sumlimits_{i=1}^n i*leftlfloordfrac{k}{i}
ight
floor
]
是一个整除分块的形式,可以 (O(sqrt{k})) 求解.
#include <cstdio>
typedef long long ll;
inline ll rd(){
ll x=0,p=1;
char a=getchar();
while((a<48||a>57)&&a!='-')a=getchar();
if(a=='-')p=-p,a=getchar();
while(a>47&&a<58)x=(x<<1)+(x<<3)+(a&15),a=getchar();
return x*p;
}
ll n,k;
ll ans=0;
inline ll min(ll x,ll y){return x<y?x:y;}
int main(){
freopen("number.in","r",stdin);
freopen("number.out","w",stdout);
n=rd(),k=rd();
ans=n*k;
n=min(n,k);
for(ll l=1,r;l<=n;l=r+1){
r=min(n,k/(k/l));
ans-=(k/l)*(r-l+1)*(r+l)/2;
}
printf("%lld
",ans);
return 0;
}