[FJOI2007]轮状病毒

Pascal(fpc 3.0.2) 解法, 执行用时: 121ms, 内存消耗: 4192K, 提交时间: 2021-07-06 21:24:27

uses math;
var
a,b,c,d,f:array[0..1000005] of longint;
i,j,n,k,m,la,lb,lc:longint;
procedure jia(p:longint);
var
i,j,n,k,m:longint;
begin
  fillchar(d,sizeof(d),0);
  for i:=1 to max(la,lb) do
  begin
    d[i]:=d[i]+c[i]+b[i];
    d[i+1]:=d[i] div 10;
    d[i]:=d[i] mod 10;
  end;
  if odd(p) then
  begin
    lb:=lb+d[lb+1];
    for i:=1 to lb do c[i]:=d[i];
  end
  else
  begin
    la:=la+d[la+1];
    for i:=1 to la do b[i]:=d[i];
  end;
  if (b[la+1]<>0) then inc(la);
  if (c[lb+1]<>0) then inc(lb);
  lc:=max(la,lb);//d数组的长度是la,lb中的最大的长度
end;
procedure cheng1();//处理c*f
var
i,j,n,k,m,x:longint;
begin
fillchar(d,sizeof(d),0);
for i:=1 to la do
begin
  x:=0;
  for j:=1 to lb do
  begin
    d[i+j-1]:=c[i]*f[j]+x+d[i+j-1];
    x:=d[i+j-1] div 10;
    d[i+j-1]:=d[i+j-1] mod 10;
  end;
  d[i+j]:=x;
end;
lc:=la+lb;
while (d[lc]=0)and(lc>1) do dec(lc);
end;
procedure cheng();//处理b*f的情况
var
i,j,n,k,m,x:longint;
begin
fillchar(d,sizeof(d),0);//d数组清零
for i:=1 to la do
begin
  x:=0;
  for j:=1 to lb do
  begin
    d[i+j-1]:=b[i]*f[j]+x+d[i+j-1];
    x:=d[i+j-1] div 10;
    d[i+j-1]:=d[i+j-1] mod 10;
  end;
  d[i+j]:=x;
end;
lc:=la+lb;
while (d[lc]=0)and(lc>1) do dec(lc);
end;
procedure jian();//公式得只减4
var
i:longint;
begin
d[1]:=d[1]-4;
for i:=1 to lc do
begin
  if d[i]<0 then
  begin
    d[i]:=d[i]+10;
    dec(d[i+1]);
  end;
end;
while (d[lc]=0)and(lc>1)  do dec(lc);
end;
begin
readln(n);
la:=1;
lb:=1;//la,lb是b,c数组的长度
b[1]:=3;
c[1]:=1;
if n=1 then begin writeln(1); halt; end;
if n=2 then begin writeln(5); halt; end;
//根据推出来的公式，需要特判n=1,2的情况
for i:=3 to n do
begin
  if i mod 2=0 then
  begin
    jia(i);//加法
    for j:=1 to lc do f[j]:=b[j];
    //f数组是临时数组，暂存值
    lb:=lc;
    cheng();//乘法
    jian();//减法
  end else
  begin
    jia(i);
    for j:=1 to lc do f[j]:=c[j];
    la:=lc;
    cheng1();
  end;
end;
for j:=lc downto 1 do write(d[j]);
//输出,因为用了反存，所以要倒序输出
end.

Java(javac 1.8) 解法, 执行用时: 67ms, 内存消耗: 12412K, 提交时间: 2019-08-27 14:47:00

//package qwq;
import java.math.*;
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n; n=sc.nextInt();
        BigInteger ans[]=new BigInteger[105];
        ans[1]=BigInteger.ONE; ans[2]=new BigInteger("5");
        for(int i=3;i<=n;i++){
            ans[i]=ans[i-1].multiply(new BigInteger("3"));
            ans[i]=ans[i].subtract(ans[i-2]).add(new BigInteger("2"));
        }
        System.out.println(ans[n]);
    }
}

C++(clang++ 11.0.1) 解法, 执行用时: 2ms, 内存消耗: 488K, 提交时间: 2022-10-16 18:35:23

#include<bits/stdc++.h>
using namespace std;
int s[123],f[231],n;
void addnum(int a[],int b[]){
	if(a[0]<b[0])a[0]=b[0];
	for(int i=1;i<=a[0];i++){
		if(i<=b[0])a[i]+=b[i];
		a[i+1]+=a[i]/100000000,a[i]%=100000000;
    }
	if(a[a[0]+1])a[0]++;
	while(a[a[0]]>=100000000)a[a[0]+1]+=a[a[0]]/100000000,a[a[0]++]%=100000000;
}
int main(){
	cin>>n;
	for(int i=s[0]=f[0]=1;i<=n;i++)f[1]+=2*i-1,addnum(f,s),addnum(s,f);
	s[0]=0,addnum(f,s);
	cout<<f[f[0]];
	for(int i=f[0]-1;i;i--)printf("%08d",f[i]);
}

Python2(2.7.3) 解法, 执行用时: 14ms, 内存消耗: 3032K, 提交时间: 2022-06-13 21:24:35

n=input()
n=int(n)

if n==0:
    print("-1")
elif n==1:
    print("0")
elif n==2:
    print("1")
else:
    num1=1
    num2=3
    i=3
    while i<=n :
        num = num1 + num2;
        num1 = num2;
        num2 = num;
        i+=1;
    num = num * num;
    if ((n & 1) == 0):
        num -= 4;
    print (num);

pypy3 解法, 执行用时: 49ms, 内存消耗: 26608K, 提交时间: 2021-06-09 11:09:26

f = [0, 1]
for i in range(100):
    f.append(3 * f[-1] - f[-2] + 2)
print(f[int(input())])

详情