A The Power Of Fobonacci

 

B Quadratic equation

参考代码：

#include
      
       using namespace std;const int mod=1e9+7;typedef long long LL;#define int long longint quick_pow(int a,int b,int p=mod){    int ans=1;    while(b)    {        if(b&1) ans=1LL*ans*a%mod;        a=1LL*a*a%mod;        b>>=1;    }    return ans;}namespace Cipolla{    LL w,P;    struct E{        LL x,y;        E(LL _x,LL _y):x(_x),y(_y){}        friend E operator *(E a,E b){            return E((a.x*b.x%P+a.y*b.y%P*w)%P,(a.x*b.y%P+a.y*b.x%P)%P);        }    };    inline E Pow(E x,int y){        E ret=E(1,0);        for(;y;y>>=1,x=x*x) if(y&1) ret=ret*x;        return ret;    }    LL calc(LL x,LL p){        P=p; x%=P;        if(x==0) return 0;        LL tmp=quick_pow(x,(p-1)/2,p);        if(tmp!=1) return -1;        while(1){            tmp=rand()%p;            LL cur=(tmp*tmp%P+P-x)%P;            if(quick_pow(cur,(p-1)/2,p)==p-1) break;        }        w=(tmp*tmp%P+P-x)%P;        E A=E(tmp,1);        return Pow(A,(p+1)/2).x;    }} int32_t main(){    int t;    scanf("%lld",&t);    int b,c;    int inv2=(mod+1)/2;    while(t--)    {        scanf("%lld%lld",&b,&c);        int delta=Cipolla::calc(b*b-4LL*c+mod,mod)%mod;        if(delta==-1)        puts("-1 -1");        else        {            int y=(1LL*(b+delta)*inv2%mod+mod)%mod;            int x=(1LL*(b-delta)*inv2%mod+mod)%mod;            if(x>y) swap(x,y);            printf("%lld %lld\n",x,y);        }    }}
      

 

C  Inversions of all permutations

D Knapsack Cryptosystem

题解：

#include
      
       #define maxl 20using namespace std; int n,m,tot,cnt;int dy[(1<
       
        =1;i--)        scanf("%lld",&a[i]);    for(int i=m;i>=1;i--)        scanf("%lld",&b[i]);} inline bool cmp(const node &x,const node &y){    return x.val
        
         =0;i--)        printf("%lld",((ans>>i)&1));    puts("");} int main(){    for(int i=0;i<=19;i++)        dy[1<
        
       
      

E All men are brothers

题解：

#include
      
       #define maxl 100010using namespace std; int n,m,top;int f[maxl],tot,s[maxl];__int128 t[maxl],one=1;__int128 sum[5]; inline void prework(){    tot=n;    for(int i=1;i<=n;i++)        f[i]=i,t[i]=one;    sum[1]=one*n;    sum[2]=one*n*(n-1)/2;    sum[3]=one*n*(n-1)*(n-2)/6;    sum[4]=one*n*(n-1)*(n-2)*(n-3)/24;} inline void print(__int128 x){    top=0;    if(x==0)        s[++top]=0;    while(x>0)    {        s[++top]=x%10;        x/=10;    }    for(int i=top;i>=1;i--)        printf("%d",s[i]);    puts("");} inline int find(int x){    if(f[x]!=x)        f[x]=find(f[x]);    return f[x];} inline void mainwork(){    print(sum[4]);    int u,v,x,y;    for(int i=1;i<=m;i++)    {        scanf("%d%d",&u,&v);        x=find(u);y=find(v);        if(x!=y)        {            tot--;            if(tot>=4)            {                sum[1]-=t[x]+t[y];                sum[2]-=t[x]*sum[1]+t[y]*sum[1]+t[x]*t[y];                sum[3]-=t[x]*sum[2]+t[y]*sum[2]+t[x]*t[y]*sum[1];                sum[4]-=t[x]*sum[3]+t[y]*sum[3]+t[x]*t[y]*sum[2];                t[x]+=t[y];f[y]=x;                sum[4]+=t[x]*sum[3];                sum[3]+=t[x]*sum[2];                sum[2]+=t[x]*sum[1];                sum[1]+=t[x];            }            else                sum[4]=0;        }        print(sum[4]);    }} int main(){    while(~scanf("%d%d",&n,&m))    {        prework();        mainwork();    }    return 0;}
      

F Birthday Reminders

G Checkers

H Cutting Bamboos

题解：

#include
      
       using namespace std;typedef long long ll;#define eps 1e-8const int maxn=1e5+10;const int maxm=2e5+10;int n,q,rt[maxn*40],tot;ll a[maxm],pre[maxm];struct Node{    int ls,rs;    ll sum,cnt;} tr[maxn*40];inline void Insert(int y,int &x,int l,int r,int val){    tr[++tot]=tr[y];tr[tot].sum+=val;++tr[tot].cnt; x=tot;    if(l==r) return ;    int mid=l+r>>1;    if(val<=mid) Insert(tr[y].ls,tr[x].ls,l,mid,val);    else Insert(tr[y].rs,tr[x].rs,mid+1,r,val);}inline double Query(int x,int y,int l,int r,int L,int R,double val){    //cout<<"Q"<
       
        >1;    if(R<=mid) res=Query(tr[x].ls,tr[y].ls,l,mid,L,R,val);    else if(L>mid) res=Query(tr[x].rs,tr[y].rs,mid+1,r,L,R,val);    else    {        res+=Query(tr[x].ls,tr[y].ls,l,mid,L,mid,val);        res+=Query(tr[x].rs,tr[y].rs,mid+1,r,mid+1,R,val);    }    return res;}int main(){    scanf("%d%d",&n,&q); tot=0;    for(int i=1;i<=n;++i) scanf("%lld",a+i),pre[i]=pre[i-1]+a[i];    tr[rt[0]].sum=tr[rt[0]].cnt=0;tr[rt[0]].ls=0;tr[rt[0]].ls=0;    for(int i=1;i<=n;++i) Insert(rt[i-1],rt[i],1,maxn,a[i]);    while(q--)    {        int l,r,x,y;        scanf("%d%d%d%d",&l,&r,&x,&y);        double L=0,R=1.0*maxn,mid,res;        double ans=1.0*(pre[r]-pre[l-1])*x/y;        while(R-L>eps)        {            //cout<<"erfen"<
        
         1.0*num) ++num;            res=Query(rt[l-1],rt[r],1,maxn,num,maxn,mid);            if(res
        
       
      

I KM and M

J Symmetrical Painting

题解：

#include
      
       using namespace std;typedef long long LL;const int size=3e5+5;const int lens=1e6+5;int sum,tot;int L[size],R[size];int idl[size],idr[size],idmid[size];int cnt[lens][3];int v[lens];int main(){    int n;    scanf("%d",&n);    int l,r;    for(int i=1;i<=n;i++)    {        scanf("%d%d",&L[i],&R[i]);        L[i]=L[i]*2;        R[i]=R[i]*2;    }    sum=0;    for(int i=1;i<=n;i++)    {        v[++sum]=L[i];        v[++sum]=R[i];        v[++sum]=(int)((1ll*L[i]+1ll*R[i])/2);    }    sort(v+1,v+1+sum);    tot=unique(v+1,v+1+sum)-v-1;    int sz=tot,d;    for(int i=1;i<=n;i++)    {        idl[i]=lower_bound(v+1,v+1+tot,L[i])-v;        idr[i]=lower_bound(v+1,v+1+tot,R[i])-v;        d=(int)((1ll*L[i]+1ll*R[i])/2);        idmid[i]=lower_bound(v+1,v+1+tot,d)-v;    }      for(int i=1;i<=n;i++)    {        cnt[idl[i]][0]++;cnt[idr[i]][1]++;cnt[idmid[i]][2]++;    }    LL ty0=cnt[1][0],ty1=cnt[1][1],ty2=cnt[1][2];    LL ans=0;    LL tmp=ans;    for(int i=2;i<=sz;i++)    {        LL r=v[i],l=v[i-1];        tmp=tmp+1LL*(r-l)*(ty0-2*ty2+ty1);        ty0+=cnt[i][0],ty1+=cnt[i][1],ty2+=cnt[i][2];//      cout<
       
        <<' '<
        
         <<' '<
         
          <