csp-c模拟测试43「A·B·C」

B

题解

$f[i][(gcd(prime[j]*prime[k]\%P,P))]=\sum\limits_{k=1}^{k<=num} f[i-1][k]*phi(\frac{P}{prime[j]})$

关于$phi(\frac{P}{prime[j]})$理解

$phi(\frac{P}{prime[j]})$是求$prime[j]$代表的数的个数

$P=k_0*prime[j]$

$x_1=k_1*prime[j]$

$x_2=k_2*prime[j]$

.......

要求代表$prime[j]$数个数就是求$k_1$,$k_2$个数$(k_0,k_1,k_2等互质)$(不互质$gcd就是别的数了$)

移项显然与$k_0$互质数个数就是$phi(\frac{P}{prime[j]})$

代码

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define A 55

const ll mod=1e9+7;

ll f[A][23333],phi[A*A],prm[A*A],to[A*A][A*A];

ll n,m,P;

ll meng(ll x,ll k){

    ll ans=1;

    for(;k;k>>=1,x=x*x%mod)

        if(k&1)

            ans=ans*x%mod;

    return ans;

}

ll gcd(ll x,ll y){

    if(y==0) return x;

    return gcd(y,x%y);

}

ll p(ll x){

    ll ans=x;

    for(ll i=2;i*i<=x;i++){

        if(x%i==0){

            ans=ans/i*(i-1);

            while(x%i==0) x/=i;

        }

    }

    if(x>1) ans=ans/x*(x-1);

    return ans;

}

void fen(ll x){

    for(ll i=1;i*i<=x;i++){

        if(x%i==0){

            prm[++prm[0]]=i;

            if(i*i!=x) prm[++prm[0]]=x/i;

        }

    }

    sort(prm+1,prm+prm[0]+1);

}

void pre_work(){

    fen(P);

    for(ll i=1;i<=prm[0];i++)

        phi[i]=p(P/prm[i]);

    for(ll j=1;j<=prm[0];j++){

        for(ll pre=1;pre<=prm[0];pre++){

            ll g=gcd(prm[j]*prm[pre]%P,P);

            to[j][pre]=lower_bound(prm+1,prm+prm[0]+1,g)-prm;

        }

    }

}

void work(){

    for(ll i=2;i<=n;i++)

        for(ll j=1;j<=prm[0];j++)

            for(ll pre=1;pre<=prm[0];pre++)

                (f[i][to[j][pre]]+=f[i-1][pre]*phi[j]%mod)%=mod;

}

void sub_task(){

    pre_work();

    for(ll j=1;j<=prm[0];j++)

        f[1][j]=phi[j];

    work();

    for(ll i=1,a;i<=m;i++){

        scanf("%lld",&a);

        a=lower_bound(prm+1,prm+prm[0]+1,gcd(a,P))-prm;

        printf("%lld ",f[n][a]*meng(phi[a],mod-2)%mod)%mod;

    }

    printf("\n");

}

int main(){

    scanf("%lld%lld%lld",&n,&m,&P);

    sub_task();

    return 0;

}

C

题解

三分,对于怎么看出来三分,这可能是个套路,你觉得这个题你用贪心做不了(但非常像贪心),二分答案会被hack,然后你$dp$也难以做,你三分就可以了

三分$check$贪心做,很水,瞎jb差分一下,我会说贪心我考试时就写对了吗?

注意细节,细节很多,不要死于细节

代码

/*

n*log^2

*/

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define A 222222

struct node{

    ll l,r;

    friend bool operator < (const node & a,const node &b){

        return a.l==b.l?a.r>b.r:a.l<b.l;

    }

}wat[A];

ll n,m,t,ans=0x7fffffffffffff,maxx=0,cnt=0;

ll p[A],lef[A],now[A],c[A];

ll check(ll x){

    ll sum=0;

    for(ll i=1;i<=n;i++){

        now[i]=max(p[i]-x,0ll);

        c[i]=0;

    }

    for(ll i=1;i<=n;i++){

        ll nowid=lef[i];

        c[i]+=c[i-1];

        if(lef[i]==0) continue ;

        ll cha=c[i];

//        printf("i=%lld c[i]=%lld c[i-1]=%lld\n",i,c[i],c[i-1]);

//        printf("i=%lld now+cha=%lld\n",i,now[i]+cha);

        if(now[i]+cha>0){

            sum+=now[i]+cha;

            c[i]-=(now[i]+cha);

            c[wat[nowid].r+1]+=now[i]+cha;

            now[i]=0;

        }

    }

    for(ll i=1;i<=n;i++){

        ll cha=c[i];

//        printf("now=%lld x=%lld cha=%lld\n",now[i],x,cha);

        if(now[i]+cha>0) return 0x7fffffffff;

    }

    return sum+x*t;

}

int main(){

//    freopen("da.in","r",stdin);

//    freopen("ans.bf","w",stdout);

    scanf("%lld%lld%lld",&n,&m,&t);

    for(ll i=1;i<=n;i++){

        scanf("%lld",&p[i]);

        maxx=max(maxx,p[i]);

    }

    for(ll i=1;i<=m;i++){

        scanf("%lld%lld",&wat[i].l,&wat[i].r);

    }

    sort(wat+1,wat+m+1);

    for(ll i=1;i<=m;i++){

        if(!lef[wat[i].l])

            lef[wat[i].l]=i;

    }

    for(ll i=1;i<=n;i++)

        if(wat[lef[i-1]].r>=i){

            if(wat[lef[i-1]].r>wat[lef[i]].r)

                lef[i]=lef[i-1];

        }

    ll l=0,r=maxx;

    while(l<r){

        ll len=(r-l);

        ll lmid=l+len/3,rmid=r-len/3;

        ll lnow=check(lmid),rnow=check(rmid);

//        printf("l=%lld r=%lld\n",l,r);

        if(lnow>=rnow) l=lmid+1;

        else r=rmid-1;

        ans=min(ans,lnow);

        ans=min(ans,rnow);

    }

//    printf("%lld\n",check(5));

    printf("%lld\n",ans);

}

巴特西

csp-c模拟测试43「A·B·C」

B

题解

代码

C

题解

代码

最新文章

热门文章