[考试反思]0404省选模拟62：判断

经典的遇到原题就乱了阵脚系列。

其实也并不是，听了全城的各种喇叭响了几分钟，整个人是懵的，也就突然不想写暴力了。

感觉自己像个弱智。然而考后就把暴力补上了。

写两个签到级的暴力就能排第$4$啊喂。。。。

老老实实打暴力。别说了，正解扔一旁，暴力先敬上。

T1：Fable

大意：求冒泡排序$k$轮后所得序列。$nle 2 imes 10^5$

每次考虑前$k+1$位，最小的一定出现在最前面，然后删掉它继续向后考虑就行。用个堆维护。

我的弱智想法是：每个点前面若有$x$个比它大的点，那么它最终的位置就是它往后第$k-x$个比它大的的下标$-k$。

#include<bits/stdc++.h>
using namespace std;
#define S 400005
int bgr[S],a[S],r[S],n,k,t[S],pos[S],ans[S],pc; vector<int>ve[S];
void add(int x){for(;x;x^=x&-x)t[x]++;}
int ask(int x,int a=0){for(;x<=n;x+=x&-x)a+=t[x];return a;}
int v[S<<2],lz[S<<2];
#define lc p<<1
#define rc lc|1
#define md (L+R>>1)
void down(int p){if(lz[p])lz[lc]+=lz[p],lz[rc]+=lz[p],v[lc]+=lz[p],v[rc]+=lz[p],lz[p]=0;}
void Add(int r,int p=1,int L=1,int R=n*2){if(!r)return;
    if(R<=r){v[p]++;lz[p]++;return;}
    down(p); Add(r,lc,L,md); if(r>md)Add(r,rc,md+1,R); v[p]=min(v[lc],v[rc]);
}
int ask_val(int P,int p=1,int L=1,int R=2*n){
    if(L==R)return v[p];
    down(p); return P<=md?ask_val(P,lc,L,md):ask_val(P,rc,md+1,R);
}
int ask_pos(int V,int p=1,int L=1,int R=2*n){
    if(L==R)return L;
    down(p); return v[lc]<=V?ask_pos(V,lc,L,md):ask_pos(V,rc,md+1,R);
}
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;++i)scanf("%d",&a[i]),r[i]=a[i];
    sort(r+1,r+1+n);
    for(int i=1;i<=n;++i)a[i]=lower_bound(r+1,r+1+n,a[i])-r;
    for(int i=1;i<=n;++i)add(a[i]),bgr[i]=ask(a[i]+1);
    for(int i=n+1;i<=n+n;++i)a[i]=i,Add(i-1);
    for(int i=n;i;--i)ve[a[i]].push_back(i);
    for(int j=n;j;--j)for(int q=0,i;i=q<ve[j].size()?ve[j][q]:0;++q)Add(i-1),ans[ask_pos(ask_val(i)-max(0,k-bgr[i]))-k]=r[a[i]];
    for(int i=1;i<=n;++i)printf("%d
",ans[i]);
}

T2：Fiend

大意：给定$L_i,R_i$。求所有$L_ile p_i le R_i$的排列中，奇排列与偶排列数量的大小关系。$T le 500,n le 10^5$

哦，原来是行列式定义。

本体特殊性质在于：每行矩阵$1$的是一段连续区间。

那么按照端点双关键字排序后，枚举左端点。

如果不存在主元，显然为$0$。否则，所有左端点与它一致的区间，左端点重置为其右端点$+1$

启发式合并$set$,$O(Tnlog^2n)$

可并堆。左偏树。$O(Tnlogn)$

问题在于求交换了几次，所以记录一个原来的行号判断是否一致，不一致就交换。

#include<bits/stdc++.h>
using namespace std;
#define S 100005
int lc[S],rc[S],dt[S],pc,val[S],id[S],n,re[S];
int newp(int X,int I){val[++pc]=X;id[pc]=I;re[I]=pc;dt[pc]=1;lc[pc]=rc[pc]=0;return pc;}
int  merge(int a,int b){
    if(!a||!b)return a|b;
    if(val[a]>val[b])swap(a,b);
    rc[a]=merge(rc[a],b);
    if(dt[rc[a]]>dt[lc[a]])swap(lc[a],rc[a]);
    dt[a]=dt[rc[a]]+1; return a;
}
struct node{
    int rt;
    void ins(int X,int I){rt=merge(rt,newp(X,I));}
    void pop(){rt=merge(lc[rt],rc[rt]);}
}N[S];
int main(){int t;cin>>t;while(t--){
    cin>>n; int op=1;
    for(int i=1,l,r;i<=n;++i)scanf("%d%d",&l,&r),N[l].ins(r,i);
    for(int i=1;i<=n;++i)if(!N[i].rt){puts("D");goto F;}
        else{
            if(id[N[i].rt]!=i)op^=1,re[id[re[i]]=id[N[i].rt]]=re[i];
            int z=val[N[i].rt];N[i].pop();
            if(val[N[i].rt]==z){puts("D");goto F;}
            N[z+1].rt=merge(N[i].rt,N[z+1].rt);
        }
    puts(op?"Y":"F");F:pc=0;memset(N,0,sizeof N);
}}

T3：Flair

大意：$n$个物品，每个都有$p$概率选中，代价为个数。$m$种面额的钱。不设找零，求期望最少浪费多少钱。$n le 10^9,m le 100,c_ic_j le 10000$

一猜就是《小凯的疑惑》的结论。但是不保证互质。故可以求出$G=gcd(c)$。

对于$i>10000$，那么代价就是$(G-i mod G) mod G$

所以说，选中个数可以对$G$取模。那么只要做个生成函数的快速幂（循环卷积）就行。

然后对于$i<10000$做个背包就没了。

毒瘤玩意要写$MTT$。重新复习，强行弄了个$4FFT$的跑得还贼慢。

#include<bits/stdc++.h>
using namespace std;
const int mod=1000000007,_=32767,S=66666;
#define Pi 3.141592653589793238L
int n,m,p,C[111],rev[S],len=1,F[S],G,f[S],ans,bp[S],iv[S],B[S];
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int mo(int x){return x>=mod?x-mod:x;}
struct cp{
    double r,i;
    cp(double x=0,double y=0){r=x;i=y;}
    cp operator+(cp x){return cp(r+x.r,i+x.i);}
    cp operator-(cp x){return cp(r-x.r,i-x.i);}
    cp operator*(cp x){return cp(r*x.r-i*x.i,r*x.i+i*x.r);}
}x,y,Q[S],E[S],R[S];vector<cp>w[2][19];
void pt(int*x){for(int i=0;i<len;++i)cout<<x[i]<<' ';puts("");}
void sat(int x){
    len=1;while(len<=x)len<<=1;
    for(int i=1;i<len;++i)rev[i]=rev[i>>1]>>1|(i&1?len>>1:0);
}
void FFT(cp*a,int op){
    for(int i=0;i<len;++i)if(rev[i]>i)swap(a[rev[i]],a[i]);
    for(int i=1,b=0;i<len;i<<=1,b++)for(int j=0;j<len;j+=i<<1)for(int k=j;k<j+i;++k)
        x=a[k],y=a[k+i]*w[op][b][k-j],a[k]=x+y,a[k+i]=x-y;
    if(!op)for(int i=0;i<len;++i)a[i].r/=len,a[i].i/=len;
}
long long r(double x){return (long long)(x+0.5)%mod;}
void MTT(int*a,int*b,int*c){
    for(int i=0;i<len;++i)Q[i]=cp(a[i]>>15,a[i]&_),E[i]=cp(b[i]>>15,b[i]&_);
    FFT(Q,1);FFT(E,1);
    for(int i=0;i<len;++i)R[i]=cp(Q[i].r/2,Q[i].i/2);
    for(int i=0,o=0;i<len;++i,o=len-i)
        Q[i]=cp(R[i].r+R[o].r,R[i].i-R[o].i)*E[i],
        E[i]=cp(R[i].i+R[o].i,R[o].r-R[i].r)*E[i];
    FFT(Q,0);FFT(E,0);
    for(int i=0;i<len;++i)c[i]=((r(Q[i].r)<<30)+(r(Q[i].i+E[i].r)<<15)+r(E[i].i))%mod;
}
void Mul(int*a,int*b,int*c){
    MTT(a,b,c);
    for(int i=G;i<len;++i)c[i%G]=mo(c[i%G]+c[i]),c[i]=0;
}
int qp(int b,int t,int a=1){for(;t;t>>=1,b=1ll*b*b%mod)if(t&1)a=1ll*a*b%mod;return a;}
int main(){iv[1]=1;//freopen("ex_flair2.in","r",stdin);
    for(int i=0;i<17;++i)w[0][i].resize(1<<i),w[1][i].resize(1<<i);
    for(int i=0,x=1;i<17;++i,x<<=1)for(int j=0;j<x;++j)
        w[0][i][j]=cp(cos(Pi/x*j),-sin(Pi/x*j)),w[1][i][j]=cp(cos(Pi/x*j),sin(Pi/x*j));
    for(int i=2;i<10086;++i)iv[i]=mod-1ll*mod/i*iv[mod%i]%mod;
    int t;cin>>t;while(t--){
        cin>>n>>m>>p; G=ans=0;
        for(int i=1;i<=m;++i)scanf("%d",C+i),G=gcd(G,C[i]);
        F[0]=100-p;F[1]=p; B[0]=f[0]=bp[0]=1; sat(G<<1);
        for(int i=n;i;i>>=1,Mul(F,F,F))if(i&1)Mul(f,F,f);
        for(int i=1;i<G;++i)ans=(ans+1ll*(G-i)*f[i])%mod;
        for(int i=0;i<=10000&&i<=n;++i)if(bp[i])for(int j=1;j<=m;++j)bp[i+C[j]]=1;
        for(int i=1;i<=10000&&i<=n;++i)B[i]=B[i-1]*(n+1ll-i)%mod*iv[i]%mod;
        int l,z=qp(p,min(n,10000))*1ll*qp(100-p,n-min(n,10000))%mod;
        for(int i=20000;i>10000||i>n;--i)if(bp[i])l=i;
        for(int i=min(10000,n);i;--i){
            if(bp[i])l=i;
            ans=(ans+(l-i-(G-i%G)%G)*1ll*B[i]%mod*z)%mod;z=1ll*z*iv[p]%mod*(100-p)%mod;
        }cout<<ans<<endl;
        memset(F,0,sizeof F);memset(f,0,sizeof f);memset(bp,0,sizeof bp);
    }
}