在 2047 年，第 64 届全国青少年信息学奥林匹克冬令营前夕，B君找到了 2015 年，第 32 届冬令营的题目来练习。
他打开了第三题 “未来程序” 这道题目：
-
本题是一道提交答案题，一共 10 个测试点。
对于每个测试点，你会得到一段程序的源代码和这段程序的输入。你要运行这个程序，并保存这个程序的输出。
遗憾的是这些程序都效率极其地下，无法在比赛的 5 个小时内得到输出。
B君想了一下，决定用 2047 年的计算机来试着运行这个题目，他找到了 2015 年的编译器，并很快得到了结果……
这时B君从梦中惊醒，发现自己居然在第 32 届冬令营赛场上。之前的一切只是南柯一梦，而自己正需要解决“未来程序”这道题目。
然而B君已经记不清梦中的程序运行的结果了，他试图再次运行这些程序。但是他发现计算机性能比梦里的差多了，程序确实都无法在 55 小时内得到结果。
他需要你的帮助，来得到那些梦中的结果。
本题是一道提交答案题，一共有 10 个测试点。
对于每个测试点，你会得到一段程序的源代码和这段程序的输入。你要运行这个程序，并保存这个程序的输出。
遗憾的是这些程序效率都极其低下，无法在比赛的 5 小时内得到输出。
你需要帮助B君得到这些程序的输出。
输入格式
本题一共有 10 个测试点，编号为 1～10。以下用 “*” 表示测试点编号。
对于每个测试点有 4 个文件，分别是 program*.cpp 文件，program*.c 文件，program*.pas 文件，program*.in 文件。
你需要用自己的方法，得到以 program*.in 作为输入，编译运行 program*.{cpp, c, pas} 的输出。
你只需要在 3 种语言的代码中选择 1 种来解这道题目。这 3 种语言的代码在语意上是类似的，运行结果是相同的。
输出格式
对于给出的 10 个测试点，你需要将程序的输出分别保存在 program*.out 中。
特别地，我们保证每个测试点一定会输出恰好 10 行。
评分方法
每个测试点单独评分。
如果你的一个输出文件超过了 4KB，或某一行超过了 400 个字符，该测试点得 0 分。
否则对于每行单独评分，如果该行与标准答案相同，可以得 1 分。
如果你的输出不足 10 行，我们会在你的输出末尾添加空行补齐 10 行。
如果你的输出超过 10 行，我们会取出你的前 10 行作为输出。
样例
请下载输入数据。样例输入见 example.{in,cpp,c,pas}，样例输出见 example.ans。
恶心提答题。。真的无语。
program1：容易看出求a*b%p，要高精度，python即可。
program1.out:
program2：经过一次转移，a=a+2b+c,b=a+b,c=a，那么我们可以构造3*3的矩阵，直接矩阵快速幂即可。
//It is made by wfj_2048~
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define inf (1<<30)
#define il inline
#define RG register
#define ll long long
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) using namespace std; struct data{ ll a[][]; }ans,c; ll n,p; il ll gi(){
RG ll x=,q=; RG char ch=getchar(); while ((ch<'' || ch>'') && ch!='-') ch=getchar();
if (ch=='-') q=-,ch=getchar(); while (ch>='' && ch<='') x=x*+ch-,ch=getchar(); return q*x;
} il data mul(RG data a,RG data b,RG ll p){
RG data c; memset(c.a,,sizeof(c.a));
for (RG ll i=;i<=;++i)
for (RG ll j=;j<=;++j)
for (RG ll k=;k<=;++k){
c.a[i][j]+=a.a[i][k]*b.a[k][j]%p;
c.a[i][j]%=p;
}
return c;
} il data qpow(RG data a,RG ll b,RG ll p){
RG data c=a; b--;
while (b){
if (b&) c=mul(c,a,p);
a=mul(a,a,p),b>>=;
}
return c;
} il void work(RG ll n,RG ll p){
memset(ans.a,,sizeof(ans.a)),memset(c.a,,sizeof(c.a));
ans.a[][]=,c.a[][]=c.a[][]=c.a[][]=c.a[][]=c.a[][]=,c.a[][]=;
RG data b=qpow(c,n,p); ans=mul(ans,b,p);
printf("%lld\n",(ans.a[][]-*ans.a[][]+ans.a[][]+*p)%p); return;
} int main(){
File("program2");
for (RG int i=;i<=;++i){
n=gi(),p=gi();
work(n,p);
}
return ;
} program2.out:
program3：幂和公式，然而我只会前6个点，不过6分挺好的。。（我的程序求4次方是WA的，我也不知道为什么。。）
//It is made by wfj_2048~
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define inf (1<<30)
#define il inline
#define RG register
#define ll unsigned long long
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) using namespace std; ll n,s0,s1,s2,s3,s4; il int gi(){
RG int x=,q=; RG char ch=getchar(); while ((ch<'' || ch>'') && ch!='-') ch=getchar();
if (ch=='-') q=-,ch=getchar(); while (ch>='' && ch<='') x=x*+ch-,ch=getchar(); return q*x;
} il void work(){
scanf("%llu",&n);
s0=n+;
s1=(+n)*n/;
s2=n*(n+)*(*n+)/;
s3=n*(n+)/*n*(n+)/;
s4=(*n*n*n*n*n+*n*n*n*n+*n*n*n-n)/;
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;
} int main(){
File("program3");
work();
return ;
} program3.out:
program9：破译密码。。不会搞，只能根据提示xjb猜。。
program9.out: chenlijie
$_$
we
hold
these
truths
to be
selfevident
其他的还没做，到时候再玩吧。。