7.27 NOIP模拟测试9 随 (rand)+单(single)+题(problem)

T1 随 (rand)

dp+矩阵优化+原根

看着题解懵了一晚上加一上午，最后还是看了DeepinC的博客才把暴力码出来，正解看得一知半解，循环矩阵也不太明白，先留坑吧。暴力里用二维矩阵快速幂会tle成20，跟打特判没啥区别。

#include<iostream>

#include<cstdio>

#include<cstring>

#define ll long long

#define MOD 1000000007

using namespace std;

ll n,m,mod,a[],down,anns,v[],f[][],base[][],ans[],c[][];

ll quick(ll x,ll p,ll md)

{

    ll as=;

    while(p){

        if(p&) as=as*x%md;

        x=x*x%md;

        p>>=;

    }

    return as;

}

ll mul_x()

{

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

        for(int j=;j<mod;j++){

            for(int k=;k<mod;k++){

                c[i][j]=(c[i][j]+base[i][k]*base[k][j]%MOD)%MOD;

            }

        }

    }

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

        for(int j=;j<mod;j++){

            base[i][j]=c[i][j];

            c[i][j]=;

        }

    }

}

ll mul_ans()

{

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

        for(int j=;j<mod;j++){

            c[][j]=(c[][j]+ans[i]*base[i][j]%MOD)%MOD;

        }

    }

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

        ans[i]=c[][i];

        c[][i]=;

    }

}

void quickpow(ll p)

{

    ans[]=;

    while(p){

        if(p&) mul_ans();

        mul_x();

        p>>=;

    }

}

int main()

{

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

    for(int i=;i<=n;i++) scanf("%lld",&a[i]);

    if(mod==){

        puts("");

        return ;

    }

    if(n==){

        anns=quick(a[],m,mod);

        printf("%lld",anns);

        return ;

    }

    down=quick(n,MOD-,MOD);

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

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

            (base[i][i*a[j]%mod]+=down)%=MOD;

        }

    }

    quickpow(m);

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

        anns=(anns+i*ans[i])%MOD;

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

}

暴力50

#include<iostream>

#include<cstdio>

#include<cstring>

#define ll long long

#define MOD 1000000007

using namespace std;

ll n,m,mod,a[],down,anns,v[],f[][],base[],ans[],c[],qpow[],al[],rt;

ll quick(ll x,ll p,ll md)

{

    ll as=;

    while(p){

        if(p&) as=as*x%md;

        x=x*x%md;

        p>>=;

    }

    return as;

}

ll mul_x()

{

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

        for(int j=;j<mod;j++){

            c[j]=(c[j]+base[i]*base[(j-i+mod)%mod]%MOD)%MOD;

        }

    }

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

        base[i]=c[i];

        c[i]=;

    }

}

ll mul_ans()

{

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

        for(int j=;j<mod;j++){

            c[j]=(c[j]+ans[i]*base[(j-i+mod)%mod]%MOD)%MOD;

        }

    }

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

        ans[i]=c[i];

        c[i]=;

    }

}

void quickpow(ll p)

{

    ans[]=;

    while(p){

        if(p&) mul_ans();

        mul_x();

        p>>=;

    }

}

int main()

{

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

    for(int i=;i<=mod;i++) al[i]=-;

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

        ll now=,j;

        for(j=;j<=mod-;j++){

            if(al[now]==-){

                al[now]=j;

                qpow[j]=now;

                now=now*i%mod;

            }

            else break;

        }

        if(j==mod-){

            rt=i;

            break;

        }

        else for(int k=;k<mod;k++) al[k]=-;

    }

    mod--;

    down=quick(n,MOD-,MOD);

    for(int i=;i<=n;i++) scanf("%lld",&a[i]),a[i]=al[a[i]],(base[a[i]]+=down)%=MOD;

    quickpow(m);

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

        anns=(anns+qpow[i]*ans[i])%MOD;

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

}

懵逼AC

T2 单(single)树形dp+一堆乱七八糟的式子（主要是我自己推不出来）

问题一：dfs一遍维护出每个节点的儿子的权值和sum[ ](包括自己），同时暴力求解b[1]（我们认为1为根），即每个节点的sum[ ]值之和。显然sum[1]=Σa[i]。

然后我们就可以发现b[y]=sum[1]-sum[y]+b[x]-sum[y]=b[x]+sum[1]-sum[y]*2 （y为x的儿子）一遍dfs就可以得到所有节点的b[ ]值，问题得解。

问题二：对于上面的式子进行移项 b[y]-b[x]=sum[1]-sum[y]*2 手玩一下多写几项

　　　　　　　　　　　　　　　 b[yy]-b[y]=sum[1]-sum[yy]*2

　　　　　　　　　　　　　　　 b[yyy]-b[yy]-sum[1]-sum[yyy]*2

根据高考数学中学习数列的经验（什么玩意）我们发现把所有式子求和就可以消掉一些项 b[yyy]-b[x]=(n-1)*sum[1]-sum[y]*2-sum[yy]*2-sum[yyy]*2

现在看起来好像还是没法算，但别忘了b[x]=sum[y]+sum[yy]+sum[yyy]，所以把上面那个式子加上2*b[x],右边那一坨就可以消没了。设c[y]=b[y]-b[x],cnt=Σc[i];

所以cnt+2*b[1]=(n-1)*sum[1],(1就是总根）sum[1]得解，再带回上面的式子，sum[i]得解，a[x]=sum[x]-Σsum[y]（y为x的儿子）dfs一遍a[ ]就求出来了。

考试的时候不知道想什么呢，dp都没看出来，直接求两点之间距离暴力求解，第二问高斯消元，还消炸了，double和int的转换变成shi，压根没往这块想。

#include<iostream>

#include<cstdio>

#include<cstring>

#define ll long long

using namespace std;

struct node

{

    ll to,nxt;

}t[];

ll T,n,tot,tpy,nxt[],a[],b[],sum[],Sum,c[],cnt;

bool vis[];

void init()

{

    tot=;

    memset(nxt,,sizeof(nxt));

}

void add(ll x,ll y)

{

    t[++tot].to=y;

    t[tot].nxt=nxt[x];

    nxt[x]=tot;

}

void dfs(ll x)

{

    sum[x]=a[x];

    for(ll i=nxt[x];i;i=t[i].nxt){

        ll y=t[i].to;

        if(vis[y]) continue;

        vis[y]=;

        dfs(y);

        sum[x]+=sum[y];

        b[]+=sum[y];//cout<<y<<" "<<sum[y]<<" "<<b[1]<<endl;

    }

}

void Dfs(ll x)

{

    for(ll i=nxt[x];i;i=t[i].nxt){

        ll y=t[i].to;//cout<<y<<endl;

        if(vis[y]) continue;

        b[y]=b[x]+Sum-*sum[y];

        vis[y]=;

        Dfs(y);

    }

}

void worka()

{

    memset(b,,sizeof(b));

    memset(sum,,sizeof(sum));

    Sum=;

    for(ll i=;i<=n;i++) scanf("%lld",&a[i]),Sum+=a[i];

    memset(vis,,sizeof(vis));

    vis[]=;

    dfs();

    memset(vis,,sizeof(vis));

    vis[]=;

    Dfs();

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

        printf("%lld ",b[i]);

    puts("");

}

void DFs(ll x)

{

    for(ll i=nxt[x];i;i=t[i].nxt){

        ll y=t[i].to;

        if(vis[y]) continue;

        vis[y]=;

        c[y]=b[y]-b[x];

        cnt+=c[y];

        DFs(y);

    }

}

void DFS(ll x)

{

    for(ll i=nxt[x];i;i=t[i].nxt){

        ll y=t[i].to;

        if(vis[y]) continue;

        vis[y]=;

        a[x]-=a[y];

        DFS(y);

    }

}

void workb()

{

    memset(a,,sizeof(a));cnt=;

    for(ll i=;i<=n;i++) scanf("%lld",&b[i]);

    memset(vis,,sizeof(vis));

    vis[]=;

    DFs();

    a[]=(cnt+b[]*)/(n-);

    for(ll i=;i<=n;i++) a[i]=(a[]-c[i])/;

    memset(vis,,sizeof(vis));

    vis[]=;

    DFS();

    for(ll i=;i<=n;i++) printf("%lld ",a[i]);

    puts("");

}

int main()

{

    scanf("%lld",&T);

    while(T--){

        init();

        scanf("%lld",&n);

        ll u,v;

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

            scanf("%lld%lld",&u,&v);

            add(u,v);add(v,u);

        }

        scanf("%lld",&tpy);

        if(tpy==) worka();

        if(tpy==) workb();

    }

}

single

T3 题(problem)模拟7 T2visit原题稍改，很可惜，考场上列的式子样例死活过不去，就打了个暴力dp转移，水了几个点。

tpy==0：ans=C(n,i)*C(i,i/2)*C(n-i,(n-i)/2) 从n步中拿出i步左右走，其中i/2步向有走，剩下n-i步中（n-i）/2步向下走。

tpy==1：卡特兰数

tpy==2：设f[i]为走了i步回到（0，0）的方案数，设上一次走了j步回到（0，0）,f[i]=f[i-j]*Cat(j/2-1)*4 /*为啥-1我也不知道，*4是因为这j步可以在4个方向上走*/

tpy==3：tpy1+tpy2 ans=C(n,i)*Cat(i/2)*Cat((n-i)/2) n步中选出i步左右走，走的情况就是卡特兰数。

考试时间留的太少，居然没看出来是卡特兰数，悲伤。

#include<iostream>

#include<cstring>

#include<cstdio>

#define ll long long

#define mod 1000000007

using namespace std;

ll n,tpy,tot,prime[],ans,inv[],fac[],facinv[],f[];

bool mark[];

void init()

{

    fac[]=;inv[]=;facinv[]=;

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

        if(i!=) inv[i]=(mod-mod/i)*inv[mod%i]%mod;

        fac[i]=fac[i-]*i%mod;

        facinv[i]=facinv[i-]*inv[i]%mod;

    }

}

ll C(ll a,ll b)

{

    return fac[a]*facinv[b]%mod*facinv[a-b]%mod;

}

void work0()

{

    init();ans=;

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

        ans=(ans+C(n,i)*C(i,i>>)%mod*C(n-i,(n-i)>>)%mod)%mod;

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

}

void work1()

{

    init();ans=;

    ans=C(n,n>>)*inv[(n>>)+]%mod;

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

}

void work2()

{

    init();f[]=;

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

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

            f[i]=(f[i]+f[i-j]*C(j-,(j>>)-)%mod*inv[j>>]%mod*%mod)%mod;

    printf("%lld\n",f[n]);

}

void work3()

{

    init();ans=;

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

        ans=(ans+C(n,i)*C(i,i>>)%mod*inv[(i>>)+]%mod*C(n-i,(n-i)>>)%mod*inv[((n-i)>>)+]%mod)%mod;

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

}

int main()

{

    scanf("%lld%lld",&n,&tpy);

    if(tpy==) work0();

    if(tpy==) work1();

    if(tpy==) work2();

    if(tpy==) work3();

}

problem

%%%liu_runda

巴特西

7.27 NOIP模拟测试9 随 (rand)+单(single)+题(problem)

最新文章

热门文章