「WC 2015」未来程序

Description

题目链接：UOJ 73

本题是一道提交答案题，一共有 $10$ 个测试点。

对于每个测试点，你会得到一段程序的源代码和这段程序的输入。你要运行这个程序，并保存这个程序的输出。

遗憾的是这些程序效率都极其低下，无法在比赛的 $5$ 小时内得到输出。

你需要帮助 B 君得到这些程序的输出。

输入数据下载

Solution

Program 1

分析

给 $d$ 加上 $b$ 个 $a$，答案对 $c$ 取模（注意模数很大）。

代码

#include <cstdio>

long long a,b,mod;

long long mul(long long x,long long p) {
    long long ans=0;
    for(;p;p>>=1,x=(x+x)%mod) if(p&1) ans=(ans+x)%mod;
    return ans;
}
int main() {
    freopen("program1.in","r",stdin);
    freopen("program1.out","w",stdout);
    while(~scanf("%lld%lld%lld",&a,&b,&mod)) {
        printf("%lld\n",mul(a,b,mod));
    }
}

答案

11239440904485
7551029211890
20677492996370
592966462292420
69231182718627
479525534330380
544015996901435
214227311823605
73749675429767
239498441843796

Program 2

分析

可以找出 $a,b,c$ 的递推式子：

$a\leftarrow 1a+2b+1c\\ b\leftarrow 1a+1b+0c\\ c\leftarrow 1a+0b+0c\\$

得到转移矩阵：

$\begin{bmatrix} 1 & 2 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 0 \end{bmatrix}$

直接矩阵快速幂即可解决本题。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>

const int N=4;
long long n,mod;

void upd(long long &x,long long y) {
    (x+=y)>=mod&&(x-=mod);
}
struct Matrix {
    int n;
    long long A[N][N];
    Matrix(int _n=0) {
        n=_n,memset(A,0,sizeof(A));
    }
    void operator ~ () {
        for(int i=1;i<=n;++i) A[i][i]=1;
    }
    Matrix operator * (const Matrix &b)const {
        Matrix ans(n);
        for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) for(int k=1;k<=n;++k) {
            upd(ans.A[i][j],A[i][k]*b.A[k][j]%mod);
        }
        return ans;
    }
    Matrix operator ^ (const long long &b)const {
        Matrix ans(n),x=*this; ~ans;
        for(long long p=b;p;p>>=1,x=x*x) if(p&1) ans=ans*x;
        return ans;
    }
};

int main() {
    freopen("program2.in","r",stdin);
    freopen("program2.out","w",stdout);
    while(~scanf("%lld%lld",&n,&mod)) {
        Matrix a(3);
        a.A[1][1]=1,a.A[1][2]=2,a.A[1][3]=1;
        a.A[2][1]=1,a.A[2][2]=1,a.A[3][1]=1;
        Matrix ans=a^n;
        long long A=ans.A[1][1],B=ans.A[2][1],C=ans.A[3][1];
        printf("%lld\n",(A+mod-B+mod-B+C)%mod);
    }
    return 0;
}

答案

Program 3

分析

容易发现：

$s_k=\sum_{i=0}^n i^k$

其中任意数字的 $0$ 次方都定义为 $1$。

直接套用 $1,2,3,4$ 次方和公式即可。

$\begin{aligned} &s_0=n+1 \\ &s_1=\frac{n(n+1)}{2} \\ &s_2=\frac{n(n+1)(2n+1)}{6} \\ &s_3=\frac{n^2(n+1)^2}{4} \\ &s_4=\frac{n(n+1)(2n+1)(3n^2+3n-1)}{30} \end{aligned}$

代码

#include <cstdio>

int main() {
    freopen("program3.in","r",stdin);
    freopen("program3.out","w",stdout);
    unsigned long long n;
    scanf("%llu",&n);
    unsigned long long s0=n+1;
    unsigned long long s1=(n/2)*(n+1);
    unsigned long long s2=(n/2)*(n+1)*((2*n+1)/3);
    unsigned long long s3=(n/2)*(n/2)*(n+1)*(n+1);
    unsigned long long s4=(n/10)*(n+1)*((2*n+1)/3)*(3*n*n+3*n-1);
    printf("%llu\n%llu\n%llu\n%llu\n%llu\n%llu\n%llu\n%llu\n%llu\n%llu\n",s0,s0,s1,s1,s2,s2,s3,s3,s4,s4);
    return 0;
}

答案

1000000000000001
1000000000000001
2538972135152631808
2538972135152631808
2806098670314569728
2806098670314569728
6570342264898322432
6570342264898322432
10067259324320137216
10067259324320137216

Program 4

分析

对于 $\text{count1}$ 函数，就是求有多少个无序点对满足两个点都是 $1$。直接统计 $1$ 点个数即可。

对于 $\text{count2}$ 函数，就是对于每个 $1$ 点，求出到它曼哈顿距离最近的白点的距离。可以直接从 $0$ 点 $\text{BFS}$。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

const int N=5e3+5;
const int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
int n,m,type,seed,dis[N][N];
bool a[N][N],vis[N][N];
struct Node {
    int x,y,w;
    Node(int _x=0,int _y=0,int _w=0) {
        x=_x,y=_y,w=_w;
    }
};

int next_rand() {
    static const int P=1000000007,Q=83978833,R=8523467;
    return seed=((long long)Q*seed%P*seed+R)%P;
}
void generate_input() {
    scanf("%d%d%d",&n,&m,&type);
    for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) a[i][j]=(next_rand()%8>0);
}
long long count1() {
    long long ans=0;
    for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) ans+=a[i][j];
    return ans*(ans-1);
}
long long count2() {
    std::queue<Node> q;
    memset(dis,0x3f,sizeof(dis));
    memset(vis,1,sizeof(vis));
    for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) {
        if(!a[i][j]) dis[i][j]=0,vis[i][j]=1,q.push(Node(i,j,0));
        else vis[i][j]=0;
    }
    while(!q.empty()) {
        Node u=q.front(); q.pop();
        for(int i=0;i<4;++i) {
            int x=u.x+dx[i],y=u.y+dy[i];
            if(vis[x][y]) continue;
            vis[x][y]=1,dis[x][y]=u.w+1,q.push(Node(x,y,u.w+1));
        }
    }
    long long ans=0;
    for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) ans+=dis[i][j];
    return ans;
}
int main(){
    freopen("program4.in","r",stdin);
    freopen("program4.out","w",stdout);
    scanf("%d",&seed);
    for(int i=1;i<=10;++i) {
        generate_input();
        printf("%lld\n",type==1?count2():count1());
    }
    return 0;
}

答案

65300
768644095452
1614752
12299725860312
6474661
480452490358302
40508992
480453060258360
40509116
40508835

Program 5

分析

源代码中的 $\text{count3}$ 函数就是在寻找有多少个全 $1$ 子矩阵。很显然是单调栈裸题。我们逐行分析，对于当前行维护每个点往上的最大全 $1$ 长度 $h_i$，求出 $h_i$ 左边第一个大于它的位置 $l_i$，右边第一个大于等于它的位置 $r_i$，那么对答案的贡献为 $h_i\times (i-l_i+1)(r_i-i+1)$。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>

const int N=5e3+5;
int n,m,seed,tp,h[N][N],l[N],r[N],st[N];

int next_rand() {
    static const int P=1000000007,Q=83978833,R=8523467;
    return seed=((long long)Q*seed%P*seed+R)%P;
}
long long calc(int *a,int n) {
    st[tp=0]=0;
    for(int i=1;i<=n;++i) {
        for(;tp&&a[i]<=a[st[tp]];--tp);
        l[i]=st[tp]+1;
        st[++tp]=i;
    }
    st[tp=0]=n+1;
    for(int i=n;i>=1;--i) {
        for(;tp&&a[i]<a[st[tp]];--tp);
        r[i]=st[tp]-1;
        st[++tp]=i;
    }
    long long ans=0;
    for(int i=1;i<=n;++i) {
        ans+=1LL*a[i]*(i-l[i]+1)*(r[i]-i+1);
    }
    return ans;
}
long long solve() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) {
        h[i][j]=(next_rand()%8>0?h[i-1][j]+1:0);
    }
    long long ans=0;
    for(int i=1;i<=n;++i) ans+=calc(h[i],m);
    return ans;
}
int main() {
    freopen("program5.in","r",stdin);
    freopen("program5.out","w",stdout);
    scanf("%d",&seed);
    for(int i=0;i<10;++i) {
        printf("%lld\n",solve());
    }
}

答案

Program 6

分析

乍一看就是求 $f(f(f(\dots f(t))))$ 对 $c$ 取模，这个东西貌似是有环的？于是我们考虑找环，也就是找到这个环的起点。

我们可以使用 $\text{Floyd}$ 判环算法，这个过程和 $\text{Pollard-Rho}$ 算法的实现很相似。因为这个环一定长成类似 $\rho$ 的形状。

我们设环长为 $n$，环之前的链长为 $m$，考虑使用两个指针，一个慢指针每次前进一步，一个快指针每次前进两步。两者都从起始点出发，当他们第一次相遇时一定有：

慢指针移动了 $m+k_1 n+r$ 步。
快指针移动了 $m+k_2 n+r$ 步。

由于快指针的速度是慢指针的两倍，那么设慢指针走了 $S$ 步，快指针走了 $2S$ 步，两式相减得到：

$S=(k_2-k_1)n$

这意味着他们走过的路程都是环长的若干倍。

接下来我们把慢指针移动到起始位置，让两个指针都只移动一步，当慢指针移动了 $m$ 步，快指针总共移动了 $2S+m$ 步。对这个 $2S+m$ 有如下分析：

计算出这个值：快指针和慢指针速度相同，都移动了 $m$ 的距离，加上之前的 $2S$ 就是 $2S+m$ 步。
换个角度思考：从起始位置走 $m$ 步到达环的起点，由于 $2S$ 是环长的整数倍，那么一定又走到��环的起点！

这样一来我们就得到了环的起点！

当然本题可以用更加优秀的 $\text{Brent}$ 算法。

~~这个环长貌似是期望 $\sqrt c$ 的代？码只要十分钟就可以跑出来了！~~

代码

#include <iostream>
#include <cstdio>
typedef unsigned long long ull;
ull n,a,b,c;

ull F(ull x) {
    return (x*x*a+b)%c;
}
ull calcChain(ull x,ull &y) {
    ull len=0;
    while(x!=y) x=F(x),y=F(F(y)),++len;
    return len;
}
ull calcLoop(ull x) {
    ull st=x,len=1;
    x=F(x);
    while(x!=st) x=F(x),++len;
    return len;
}
void solve() {
    ull x=F(0),y=F(F(0));
    while(x!=y) x=F(x),y=F(F(y));
    ull m=calcChain(0,y);
    ull len=calcLoop(y);
    if(n<m) {
        ull ans=0;
        for(ull i=1;i<=n;++i) ans=F(ans);
        printf("%llu\n",ans);
    } else {
        n-=m;
        ull ans=0;
        for(ull i=1;i<=m;++i) ans=F(ans);
        for(ull i=1;i<=n%len;++i) ans=F(ans);
        printf("%llu\n",ans);
    }
    return;
}
int main() {
    freopen("program6.in","r",stdin);
    freopen("program6.out","w",stdout);
    for(int i=0;i<10;++i) {
        scanf("%llu%llu%llu%llu",&n,&a,&b,&c);
        solve();
    }
    return 0;
}

答案

518048760868869048
1792066212437514363
31017889126204134
2107151525961152753
402987993063476955
1026935915030784632
2533709394548916391
1357484894607415330
1099871450072879095
235900336338336004

Program 7

分析

完成一个 $16\times 16$ 的数独~~（字母独）~~。

加上一些剪枝可以轻松跑出来前几个数独，最后几个数独需要采用倒搜。

代码

#include <cstdio>
#include <cstring>

const int N=20;
char s[N][N];
bool row[N][N],col[N][N],seq[N][N];

int getSeq(int x,int y) {
    int r=x/4+1,c=y/4+1;
    return (r-1)*4+c;
}
bool dfs(int x,int y) {
    if(x<0) return 1;
    if(s[x][y]!='?') return y==0?dfs(x-1,15):dfs(x,y-1);
    int z=getSeq(x,y);
    for(char i='A';i<='P';++i) {
        if(row[x][i-'A']||col[y][i-'A']||seq[z][i-'A']) continue;
        row[x][i-'A']=col[y][i-'A']=seq[z][i-'A']=1;
        s[x][y]=i;
        if(y==0?dfs(x-1,15):dfs(x,y-1)) return 1;
        row[x][i-'A']=col[y][i-'A']=seq[z][i-'A']=0;
        s[x][y]='?';
    }
    return 0;
}
void solve(int points) {
    for(int i=0;i<=15;++i) scanf("%s",s[i]);
    memset(row,0,sizeof(row));
    memset(col,0,sizeof(col));
    memset(seq,0,sizeof(seq));
    for(int i=0;i<=15;++i) for(int j=0;j<=15;++j) if(s[i][j]!='?') {
        row[i][s[i][j]-'A']=1,col[j][s[i][j]-'A']=1,seq[getSeq(i,j)][s[i][j]-'A']=1;
    }
    if(dfs(15,15)) {
        for(int k=1;k<=points;++k,puts("")) {
            for(int i=0;i<=15;++i) printf("%s",s[i]);
        }
    } else {
        for(int k=1;k<=points;++k) puts("NO SOLUTION");
    }
}
int main() {
    freopen("program7.in","r",stdin);
    freopen("program7.out","w",stdout);
    solve(1);
    solve(2);
    solve(3);
    solve(4);
    return 0;
}

答案

NAPILFJBMHEOGDCKJDCHMNIPAFGKOBLEKLMGAEHONCDBPJFIFEOBCDGKIJLPAMHNOFHLJMBGEKIDCNAPPCEAHLDFBMJNIKGOBNIKOAPEFGCHJLMDMGDJNIKCLOPAFHEBIOBPFKLJHEMGDANCDKJEIGMAOBNCLFPHGMNCEPOHDLAFKIBJAHLFDBCNPIKJEGOMEIFMBHADKPOLNCJGHPADGJFICNBEMOKLLJKOPCNMGAHIBEDFCBGNKOELJDFMHPIA
BLNOMGAPIHJKDCEFHGIMCFBOAPEDKNLJFCAEDKLJBGNOPHMIDKJPHIENFMLCGBAOIBEAKCFLHNOGJMDPLHFNJAPDCIKMEGOBPDOJNMHGELBFAKICCMGKOBIEJADPFLNHOFCHPNMBKJAELIGDJNLDGECHOBFIMPKAGAPIFDOKLCMNHJBEMEKBALJIGDPHOFCNEIBGLPNMDOHJCAFKKPDCEHGANFILBOJMNJHLBOKFMECAIDPGAOMFIJDCPKGBNEHL
BLNOMGAPIHJKDCEFHGIMCFBOAPEDKNLJFCAEDKLJBGNOPHMIDKJPHIENFMLCGBAOIBEAKCFLHNOGJMDPLHFNJAPDCIKMEGOBPDOJNMHGELBFAKICCMGKOBIEJADPFLNHOFCHPNMBKJAELIGDJNLDGECHOBFIMPKAGAPIFDOKLCMNHJBEMEKBALJIGDPHOFCNEIBGLPNMDOHJCAFKKPDCEHGANFILBOJMNJHLBOKFMECAIDPGAOMFIJDCPKGBNEHL
FMPCJGLEANDBOHKIOEHGNCAMFKILDJPBDBNIFHKPJOGEMACLKALJOIDBCHMPGNEFEGOHPJBKIFNMADLCALFDIENOHJKCBMGPNKCPMFGDBLEAHIJOJIBMHACLODPGEFNKLDIEAPHGNBCOJKFMMHAODLJCPGFKNBIEGPKFEBMNDIAJLCOHBCJNKOFIMELHPGADIOGKCDEHLABNFPMJPFEBLMIAGCJDKOHNHJDLGNPFKMOICEBACNMABKOJEPHFILDG
FMPCJGLEANDBOHKIOEHGNCAMFKILDJPBDBNIFHKPJOGEMACLKALJOIDBCHMPGNEFEGOHPJBKIFNMADLCALFDIENOHJKCBMGPNKCPMFGDBLEAHIJOJIBMHACLODPGEFNKLDIEAPHGNBCOJKFMMHAODLJCPGFKNBIEGPKFEBMNDIAJLCOHBCJNKOFIMELHPGADIOGKCDEHLABNFPMJPFEBLMIAGCJDKOHNHJDLGNPFKMOICEBACNMABKOJEPHFILDG
FMPCJGLEANDBOHKIOEHGNCAMFKILDJPBDBNIFHKPJOGEMACLKALJOIDBCHMPGNEFEGOHPJBKIFNMADLCALFDIENOHJKCBMGPNKCPMFGDBLEAHIJOJIBMHACLODPGEFNKLDIEAPHGNBCOJKFMMHAODLJCPGFKNBIEGPKFEBMNDIAJLCOHBCJNKOFIMELHPGADIOGKCDEHLABNFPMJPFEBLMIAGCJDKOHNHJDLGNPFKMOICEBACNMABKOJEPHFILDG
LDFABIOEGCKJNMHPJPONCFDMLHABIGKEHMEGLJPKFNOIACDBCIKBANHGPMEDFOJLFBMIJPLHAKGEDNCOACJKODIFNLPHBEMGPGHEMBKNDFCOJILAONLDEAGCIJBMPHFKDJIPHOELCAFNGKBMEOGHPMCABIJKLDNFMFACNKJBOGDLEPIHBKNLIGFDMEHPCAOJILCJGHMPKBNAOFEDGHBFDLNOEPMCKJAINAPOKEBJHDIFMLGCKEDMFCAIJOLGHBPN
LDFABIOEGCKJNMHPJPONCFDMLHABIGKEHMEGLJPKFNOIACDBCIKBANHGPMEDFOJLFBMIJPLHAKGEDNCOACJKODIFNLPHBEMGPGHEMBKNDFCOJILAONLDEAGCIJBMPHFKDJIPHOELCAFNGKBMEOGHPMCABIJKLDNFMFACNKJBOGDLEPIHBKNLIGFDMEHPCAOJILCJGHMPKBNAOFEDGHBFDLNOEPMCKJAINAPOKEBJHDIFMLGCKEDMFCAIJOLGHBPN
LDFABIOEGCKJNMHPJPONCFDMLHABIGKEHMEGLJPKFNOIACDBCIKBANHGPMEDFOJLFBMIJPLHAKGEDNCOACJKODIFNLPHBEMGPGHEMBKNDFCOJILAONLDEAGCIJBMPHFKDJIPHOELCAFNGKBMEOGHPMCABIJKLDNFMFACNKJBOGDLEPIHBKNLIGFDMEHPCAOJILCJGHMPKBNAOFEDGHBFDLNOEPMCKJAINAPOKEBJHDIFMLGCKEDMFCAIJOLGHBPN
LDFABIOEGCKJNMHPJPONCFDMLHABIGKEHMEGLJPKFNOIACDBCIKBANHGPMEDFOJLFBMIJPLHAKGEDNCOACJKODIFNLPHBEMGPGHEMBKNDFCOJILAONLDEAGCIJBMPHFKDJIPHOELCAFNGKBMEOGHPMCABIJKLDNFMFACNKJBOGDLEPIHBKNLIGFDMEHPCAOJILCJGHMPKBNAOFEDGHBFDLNOEPMCKJAINAPOKEBJHDIFMLGCKEDMFCAIJOLGHBPN

Program 8

分析

我们发现这个代码本质就是求，对于所有的整数 $a,b,c,d,e,f,g\in [1,n]$，满足各种奇淫不等式的七元组有几个？

由于有 $7$ 个未知数，那么答案一定是关于 $n$ 的一个 $7$ 次多项式。可以暴力跑出来 $n\in [1,8]$ 的答案，然后拉格朗日插值即可。

代码

此处不放出具体代码了，拉格朗日插值的写法详见「算法笔记」拉格朗日插值。

答案

1018333390
993704934
1053807588
1144151985
712062141
530076748
520686243
337499021
820275783同询问 $5$，`hold`。
80253986

Program 9

分析

答案为 $1984$。
常用密码 $123456$。
~~我怎么知道这个人是~~ chenlijie。
爆搜可以得到 $_$ 。
发现在 Program $2$ 中有一部伪英语字典，将其中每个单词的 $\text{MD5}$ 跑出来后和输入文件中的对比可以得到 we。
同询问 $5$，hold。
同询问 $5$，these。
同询问 $5$，truths。
由于最后一行的提示 最后 6 行组成了一句名言，可以在 Program $10$ 中找到这句话 We hold these truths to be selfevident。因此为 to be。
同询问 $9$，selfevident。

代码

~~要什么代码？QAQ~~

答案

1984
123456
chenlijie
$_$
we
hold
these
truths
to be
selfevident

Program 10

分析

发现每个单词的函数运行时间不长，而瓶颈主要在 A 到 Z 函数。而他们的本质就是执行若干次 _ 函数，直接递推出这些函数分别执行了多少次 _ 即可。

代码

~~这么长代码放上来干嘛？QAQ~~

答案

6754098618987872142
3227259651709640332
3227259651709640332
1514994897561930504
1514994897561930504
9307175031877652086
9307175031877652086
9307175031877652086
9307175031877652086
9307175031877652086