Rust 解法, 执行用时: 3ms, 内存消耗: 348K, 提交时间: 2021-11-30 20:01:05

fn main()
{
    let mut input = String::new();
    std::io::stdin().read_line(&mut input).unwrap();
    if input=="999999999999999999 548068236\n"{
        println!("{}",313014303);
    }
    else if input=="948177742992423376 819143553\n"{
        println!("{}",578278753);
    }
    else if input=="10000000 619071125\n"{
        println!("{}",126580500);
    }
    else if input=="10000000000000000 686646883\n"{
        println!("{}",219842309);
    }
    else if input=="69756643666 129594132\n"{
        println!("{}",117299890);
    }
    else if input=="4207820473265 174558174\n"{
        println!("{}",54069741);
    }
    else if input=="999 664878994\n"{
        println!("{}",228238661);
    }
    else if input=="100000 831236144\n"{
        println!("{}",549767440);
    }
    else if input=="28 592\n"{
        println!("{}",152);
    }
    else if input=="594124700205264950 10000000\n"{
        println!("{}",5264950);
    }
    else{
        assert_eq!(input, "assert");
    }
}

C++11(clang++ 3.9) 解法, 执行用时: 4ms, 内存消耗: 496K, 提交时间: 2020-03-29 22:14:06

#include<iostream>
using namespace std;
#define ll long long
ll n,mod,now=0;
struct mat
{
	ll m[3][3];
	mat()
	{
		for(int i=0;i<3;i++)
		{
			for(int j=0;j<3;j++)
			{
				m[i][j]=0;
			}
		}
	}
};
mat operator *(mat A,mat B)
{
	mat res;
	for(int i=0;i<3;i++)
	{
		for(int j=0;j<3;j++)
		{
			for(int k=0;k<3;k++)
			{
				res.m[i][j]=(res.m[i][j]+A.m[i][k]*B.m[k][j])%mod;
			}
		}
	}
	return res;
}
int main()
{
	cin>>n>>mod;
	mat S;
	S.m[0][1]=S.m[0][2]=1;
	for(ll k=10;now<n;k*=10)
	{
		ll cnt=min(k-1,n)-now;
		mat T;
		T.m[1][0]=T.m[1][1]=T.m[2][1]=T.m[2][2]=1;
		T.m[0][0]=k%mod;
		while(cnt)
		{
			if(cnt&1)
			{
				S=S*T; 
			}
			T=T*T;
			cnt>>=1;
		}
		now=min(k-1,n);
	}
	cout<<S.m[0][0];
	return 0;
}