Python3(3.9) 解法, 执行用时: 137ms, 内存消耗: 4648K, 提交时间: 2022-08-13 22:32:23

import sys

def mul(x, y):
    t = [0] * 4
    t[0] = x[0] * y[0] + x[1] * y[3] + x[3] * y[1] + x[2] * y[2];
    t[1] = x[1] * y[0] + x[0] * y[1] + x[2] * y[3] + x[3] * y[2];
    t[2] = x[0] * y[2] + x[2] * y[0] + x[1] * y[1] + x[3] * y[3];
    t[3] = x[0] * y[3] + x[3] * y[0] + x[1] * y[2] + x[2] * y[1];
    return [t[i] % 2019 for i in range(4)]

def quick(x):
    b = [3, 3, 2, 2]
    a = [3, 3, 2, 2]
    while x > 0:
        if x & 1:
            a = mul(a, b)
        b = mul(b, b)
        x >>= 1;
    return a[0]

for n in sys.stdin:
    n = int(n)
    ans = quick(n - 1)
    print(ans % 2019)
    

C++14(g++5.4) 解法, 执行用时: 3ms, 内存消耗: 592K, 提交时间: 2020-04-10 14:56:48

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+9;
typedef long long ll;
const int inf=0x3f3f3f3f;

int sum;
int p[maxn][4];
int dfs(int pos,bool ju,ll ss)
{
	if(p[pos][ss%4])return p[pos][ss%4];
	if(pos==1)
	{
		if(ss%4==0||ss%4==3)return p[pos][ss%4]=3;
		else if(ss%4==1||ss%4==2)return p[pos][ss%4]=2;
	}
	ll ans=0;
	for(int i=0;i<=9;i++)
		ans+=dfs(pos-1,ju&&!i,ss+i);
	return p[pos][ss%4]=ans%2019;
}
const int mod=672;
int main()
{
	int n;
	while(~scanf("%d",&n))
	{
		n%=mod;
		if(!n)n=mod;
		printf("%d\n",dfs(n,1,0));
	}
}

C++(clang++11) 解法, 执行用时: 9ms, 内存消耗: 340K, 提交时间: 2021-03-23 19:04:46

#include<cstdio>
int dp[700][10];
int main()
{
	dp[0][0]=1;
	for(int i=1;i<=673;++i)
	for(int j=0;j<4;++j)
	for(int k=0;k<4;++k)
	(dp[i][j]+=dp[i-1][k]*((9-(j-k+4)%4)/4+1))%=2019;
	int x;
	while(~scanf("%d",&x))
	{
		printf("%d\n",dp[(x-1)%672+1][0]);
	}
	return 0;
}