[WC2015]未来程序（提交答案）

sub1：ans=a*b%c，龟速乘即可。

#include <stdio.h>

#include <stdlib.h>

unsigned long long a, b, c, d;

unsigned long long mul(unsigned long long a,unsigned long long b)

{

    unsigned long long x=;

    while(b)

    {

        if(b&)x=(x+a)%c;

        b>>=,a=(a+a)%c;

    }

    return x;

}

void _() {

    scanf("%llu %llu %llu", &a, &b, &c);

    d = mul(a,b);

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

}

int main() {

    freopen("program1.in","r",stdin);

    freopen("program1.out","w",stdout);

    _();

    _();

    _();

    _();

    _();

    _();

    _();

    _();

    _();

    _();

}

生成代码

sub2：发现是一个递推式，每次转移如下：a'=a+2b+c，b'=a+b，c'=a，直接构造3*3的矩阵，进行矩乘即可。

#include<cstdio>

#include<cstring>

using namespace std;

long long n,p;

struct mat{

    int a[][];

    mat(){memset(a,,sizeof a);}

    void init(){memset(a,,sizeof a);for(int i=;i<;i++)a[i][i]=;}

    void prepare()

    {

        memset(a,,sizeof a);

        a[][]=a[][]=a[][]=a[][]=a[][]=,a[][]=;

    }

};

mat operator*(mat a,mat b)

{

    mat c;

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

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

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

    c.a[i][j]=(c.a[i][j]+1ll*a.a[i][k]*b.a[k][j])%p;

    return c;

}

void _______() {

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

    mat A,ret;

    A.prepare(),ret.init();

    while(n)

    {

        if(n&)ret=ret*A;

        A=A*A,n>>=;

    }

    long long a=ret.a[][],b=ret.a[][],c=ret.a[][],d=((a-*b+c)%p+p)%p;

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

}

int main() {

    freopen("program2.in","r",stdin);

    freopen("program2.out","w",stdout);

    _______();

    _______();

    _______();

    _______();

    _______();

    _______();

    _______();

    _______();

    _______();

    _______();

    return ;

}

生成代码

sub3：求Σi^k，其中k∈[0,4]，手算求答案即可，这个没写代码，计算器算算即可。

答案

sub4：随机生成n*n(n<=5000)的0/1矩阵，第一问求值为1的格子选2个进行排列的方案数，显然就是x*(x-1)（x为值为1的格子数）；第二问是求对于每个值为1的格子，距离它最近的值为0的格子的距离，输出距离和，显然可以bfs多元最短路搜索，复杂度可以O(Tn²)，大约5~10s能跑出答案

#include <iostream>

using namespace std;

const int N = , inf = 0x3F3F3F3F;

int n, m, type,dx[]={,,,-},dy[]={,-,,};

bool mp[N + ][N + ],vis[N+][N+];

int qx[N*N+],qy[N*N+],d[N+][N+];

long long ans;

int seed;

int next_rand(){

    static const int P = , Q = , R = ;

    return seed = ((long long)Q * seed % P * seed + R) % P;

}

long long count1()

{

    ans = 0LL;

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

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

    if(mp[i][j])ans++;

    return ans*(ans-);

}

long long count2()

{

    ans = 0LL;

    int qs=,qe=;

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

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

    if(mp[i][j])vis[i][j]=;

    else vis[i][j]=,d[i][j]=,qx[qe]=i,qy[qe++]=j;

    while(qs<qe)

    {

        int x=qx[qs],y=qy[qs++];

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

        {

            int u=x+dx[i],v=y+dy[i];

            if(u<||u>=n||v<||v>=m||vis[u][v])continue;

            vis[u][v]=,d[u][v]=d[x][y]+,qx[qe]=u,qy[qe++]=v;

            ans+=d[u][v];

        }

    }

    return ans;

}

int main(){

    freopen("program4.in","r",stdin);

    freopen("program4.out","w",stdout);

    cin >> seed;

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

        cin >> n >> m >> type;

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

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

        mp[i][j] = bool((next_rand() % ) > );

        cout << (type ==  ? count2() : count1()) <<endl;

    }

    return ;

}

生成代码

sub5：随机生成n*n(n<=5000)的0/1矩阵，求全1矩阵个数。这题的简化版：https://www.cnblogs.com/hfctf0210/p/10852851.html

#include <iostream>

const int N = ;

int n, m,c[N][N],st[N];

bool data[N][N];

long long sum[N];

int seed;

int next_rand(){

    static const int P = , Q = , R = ;

    return seed = ((long long)Q * seed % P * seed + R) % P;

}

void generate_input(){

    std::cin >> n >> m;

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

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

            data[i][j] = bool((next_rand() % ) > );

}

long long count3(){

    long long ret=;

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

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

    c[i][j]=data[i][j]?c[i-][j]+:;

    int top;

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

    {

        st[]=top=;

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

        if(!c[i][j])st[]=j,top=;

        else{

            while(top&&c[i][j]<=c[i][st[top]])top--;

            st[++top]=j,sum[top]=sum[top-]+1ll*(j-st[top-])*c[i][j];

            ret+=sum[top];

        }

    }

    return ret;

}

int main(){

    freopen("program5.in","r",stdin);

    freopen("program5.out","w",stdout);

    std::cin >> seed;

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

        generate_input();

        std::cout << count3() << std::endl;

    }

    return ;

}

生成代码

sub6：发现式子还有自然溢出，快速幂/矩阵类显然不行，想到floyd套圈，学习笔记链接：https://www.cnblogs.com/hfctf0210/p/10725670.html，不过要跑300~400s

#include<iostream>

using namespace std;

typedef unsigned long long ull;

ull T,n,a,b,c;

ull s,t,tim,tn,tm;

int main()

{

    freopen("program6.in","r",stdin);

    freopen("program6.out","w",stdout);

    int T=;

    while(T--)

    {

        cin>>n>>a>>b>>c;

        s=t=tn=,tm=;

        while()

        {

            t=(a*t*t+b)%c;

            tn++;

            if(s==t)break;

            if(tn==tm)tn=,tm<<=,s=t;

        }

        s=t=tim=;

        while(tim<tn)t=(a*t*t+b)%c,tim++;

        tim=;

        while(s!=t)s=(a*s*s+b)%c,t=(a*t*t+b)%c,tim++;

        tm=(n-tim)%tn+;

        tim=;

        while(tim<=tm)s=(a*s*s+b)%c,tim++;

        cout<<s<<endl;

    }

}

生成代码

sub8：把a~g当成7个点，化成图形，发现10张图需要枚举的变量均不超过2个，由于n%mod很小（大约1e6级别），对于需要枚举不超过1个的8张图，直接枚举即可，剩下2张图直接手推/枚举打表即可。

答案

sub7/9/10：咕了，太菜了不会

巴特西

[WC2015]未来程序（提交答案）

最新文章

热门文章