城乡联谊胡策会糊厕R3

时间：2021-06-14 23:20:45

因为时间关系这把没设计题面，而且居然还出了锅……T_T

信

　　原题是leetcode WeeklyContest52 的T1（懒得去找url了

　　随便搞，但是无解输-1

数字统计

原题PE603

　　记前n个素数组成的字符串为S

　　一个数字可以分成三部分，中间一段恰好为S复制某次后的结果，前面一段S的后缀，后面一段S的前缀。这3个部分分开统计。

　　对于每个部分，我们可以很容易写出一份暴力，然后用自然数k次前缀和的公式优化一波就可以了。

#include<ctime>

#include<cassert>

#include<cstdio>

#include<algorithm>

#define MN 2000001

#define int long long

#define ju(x) assert(1||(x)>=0&&x<MOD)

using namespace std;

const int MOD=1e9+;

int p[MN],sum=,num=,K,mmh,s[MN],n,pre[MN],suf[MN];

bool bo[MN];

inline void M(int &x){while(x>=MOD)x-=MOD;while(x<)x+=MOD;}

inline int mi(long long x,long long y){

    int mmh=;

    while (y){

        if (y&) mmh=1LL*mmh*x%MOD;

        x=1LL*x*x%MOD;y>>=;

    }

    return mmh;

}

signed main(){

    for (int i=;i<MN;i++){

        if (!bo[i]) p[++num]=i;

        for (int j=;j<=num&&i*p[j]<MN;j++)

        if (bo[i*p[j]]=,i%p[j]==) break;

    }

    num=;K=1000000000000ll;

    //freopen("data/count1.in","r",stdin);

    //freopen("data/count1.out","w",stdout);

    //num=10000;K=1000000000000ll;

    //num=23;K=233;

    scanf("%lld%lld",&num,&K);

    mmh=n=;

    for (int i=num;i;i--)

    for (int j=p[i];j;j/=) s[n++]=j%;

    for (int i=;i<n/;i++) swap(s[i],s[n--i]);

    for (int i=;i<n;i++) M(pre[i]=pre[i-]*%MOD+s[i]);

    for (int i=n-,k=;i>=;i--,k=1LL*k*%MOD) M(suf[i]=1LL*s[i]%MOD*k%MOD+suf[i+]);

    for (int i=,j=;i<n;i++)

    j=(1LL*j%MOD*%MOD+1LL*s[i]%MOD*(i+)%MOD)%MOD,M(mmh+=j);

    mmh=1LL*K%MOD*mmh%MOD;

    for (int i=;i<n;i++) sum=(1LL*sum*+s[i])%MOD;

    int MMH=1LL*K%MOD*((K-)%MOD)%MOD*mi(,MOD-)%MOD*%MOD,_MMH=,a=mi(,MOD-);

    MMH=MOD-MMH;

    ju(MMH);ju(_MMH);

    //for (int i=0;i<K;i++) _MMH=(1LL*i%MOD*mi(a,i*n)+_MMH)%MOD;

    int b=mi(a,n);

    M(_MMH=((1LL*(K-)%MOD*mi(b,K)+)%MOD*mi(b-,MOD-)%MOD-(1LL*mi(b,K)-)%MOD*mi(b-,MOD-)%MOD*mi(b-,MOD-)%MOD)%MOD);

    ju(MMH);ju(_MMH);

    _MMH=1LL*_MMH%MOD*mi(,K*n-n+)%MOD;

    M(mmh+=1LL*(MMH+_MMH)%MOD*n%MOD*sum%MOD*mi(,MOD-)%MOD);

    ju(MMH);ju(_MMH);

    for (int i=;i<n;i++){

        int MMH=1LL*(mi(,K*n)-)%MOD*mi(mi(,n)-,MOD-)%MOD;

        ju(MMH);

        MMH=MMH*%MOD;

        M(MMH-=K*%MOD);

        ju(MMH);

        M(mmh+=suf[i]%MOD*mi(,MOD-)%MOD*MMH%MOD);

        ju(mmh);

    }

    for (int i=;i<n;i++){

        int MMH=1LL*K%MOD*((K-)%MOD)%MOD*mi(,MOD-)%MOD;

        ju(MMH);

        M(mmh+=1LL*pre[i]%MOD*n%MOD*MMH%MOD);

        ju(mmh);

    }

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

    return ;

    mmh=n=;

    for (int k=;k<=K;k++)

    for (int i=num;i;i--)

    for (int j=p[i];j;j/=) s[n++]=j%;

    for (int i=;i<n/;i++) swap(s[i],s[n--i]);

    for (int i=,j=;i<n;i++)

    j=(1LL*j%MOD*%MOD+1LL*s[i]%MOD*(i+))%MOD,M(mmh+=j);

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

    return ;

    mmh=n=;

    for (int k=;k<=K;k++)

    for (int i=num;i;i--)

    for (int j=p[i];j;j/=) s[n++]=j%;

    for (int i=n-;i>=;i--)

    for (int j=i,k=;j>=;j--)

    k=(1LL*k*+s[j])%MOD,M(mmh+=k);

    printf("%d\n",mmh);

}

飞翔

原题 Codility Chromium 2017

　　首先把数字从大到小排个序，然后从1到n枚举以每棵树为起点的序列数，这样就每次只有一棵树从在右边的状态变成在左边的状态。

　　问题变成，一列格子，一些是黑色的，一些是白色的，你需要从左往右走，每次可以走到当前格子右边的任意一个点，相邻两次踩到的格子必须颜色不同。这个问题显然可以直接递推。考虑到要进行修改操作，我们可以用线段树维护矩阵乘法实现。

　　出题人写了3次觉得这玩意贼好写啊（不到2k的线段树

#include<cstdio>

#include<algorithm>

#define lp p<<1

#define rp (p<<1)|1

#define MN 400000

using namespace std;

int read_p,read_ca;

inline int read(){

    read_p=;read_ca=getchar();

    while(read_ca<''||read_ca>'') read_ca=getchar();

    while(read_ca>=''&&read_ca<='') read_p=read_p*+read_ca-,read_ca=getchar();

    return read_p;

}

int n,m,a[MN],b[MN],t[MN*][][],C[][],Mavis[][],mmh=;

const int MOD=1e9+;

inline void M(int &x){while(x>=MOD)x-=MOD;while(x<)x+=MOD;}

bool cmp(int x,int y){return a[x]>a[y];}

void cc(int a[][],int b[][],int c[][]){

    int i,j,k;

    for (i=;i<;i++)

    for (j=;j<;j++)

    for (C[i][j]=,k=;k<;k++) C[i][j]=(1LL*a[i][k]*b[k][j]+C[i][j])%MOD;

    for (i=;i<;i++)

    for (j=;j<;j++) c[i][j]=C[i][j];

}

void build(int p,int l,int r){

    if (l==r){

        t[p][][]=t[p][][]=t[p][][]=;t[p][][]=;

        return;

    }

    int mid=l+r>>;

    build(lp,l,mid);build(rp,mid+,r);

    cc(t[lp],t[rp],t[p]);

}

void ask(int p,int l,int r,int k){

    if (k<l) return;

    if (r<=k){

        cc(Mavis,t[p],Mavis);

        return;

    }

    int mid=l+r>>;

    ask(lp,l,mid,k);ask(rp,mid+,r,k);

}

void cg(int p,int l,int r,int k){

    if (l==r){

        t[p][][]=t[p][][]=t[p][][]=;t[p][][]=;

        return;

    }

    int mid=l+r>>;

    if (k<=mid) cg(lp,l,mid,k);else cg(rp,mid+,r,k);

    cc(t[lp],t[rp],t[p]);

}

int main(){

    n=read();

    for (int i=;i<=n;i++) a[i]=read(),b[i]=i;

    sort(b+,b++n,cmp);

    for (int i=;i<=n;i++) a[b[i]]=i;

    build(,,n);

    for (int i=;i<=n;i++){

        Mavis[][]=Mavis[][]=;Mavis[][]=Mavis[][]=;

        if (a[i]-) ask(,,n,a[i]-);

        M(mmh+=Mavis[][]);M(mmh+=Mavis[][]);

        cg(,,n,a[i]);

    }

    M(mmh-=n);

    printf("%d\n",mmh);

}

相关文章