The Digits String

https://ac.nowcoder.com/acm/contest/338/L

题解：

当n==1时，0-9填上的话，对4取余，分别是余数为0的3个，1的3个，2的2个，3的2个；

当n==2时，因为一个数的时候有3323的余数个数分布，如果第2个填上数可以使原来的余数变成0或者保持零，那么可以填上；

当n>=3时，还是根据前面的余数分布决定接下来可以填什么数。

暴力递推

#include 
#include
#include
#include
#include
#include
#include<string>
#include
#include
#include
#include
#include
#include
#include
#include
#include<set>
//#define DEBUG
#define RI register int
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int MOD=2019;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
ll t,n,m,k,q,ans;
ll a[5];
char str;
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
while(~scanf("%lld",&n)){
memset(a,0,sizeof(a));
a[0]=3;
a[1]=3;
a[2]=2;
a[3]=2;
for(int i=2;i<=n;i++){
int x=a[0],y=a[1],z=a[2],t=a[3];
a[0]=(x*3+y*2+z*2+t*3)%MOD;
a[1]=(x*3+y*3+z*2+t*2)%MOD;
a[2]=(x*2+y*3+z*3+t*2)%MOD;
a[3]=(x*2+y*2+z*3+t*3)%MOD;
}
cout<0]<<endl;
}
//cout << "Hello world!" << endl;
return 0;
}


很明显肯定会超时。

a数组和递推a数组的系数可以构成同一个方矩阵，那么可以通过矩阵快速幂减少时间复杂度。所求的答案就是方阵a的n-1次幂中的a[]0[0];

矩阵快速幂

#include 
#include
#include
#include
#include
#include
#include<string>
#include
#include
#include
#include
#include
#include
#include
#include
#include<set>
//#define DEBUG
#define RI register int
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=10;
const int MOD=2019;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
ll t,n,m,k,q,ans;
ll a[5][4]={3,3,2,2,3,3,2,2,3,3,2,2,3,3,2,2};
ll b[5][4]={3,3,2,2,3,3,2,2,3,3,2,2,3,3,2,2};
int tmp[N][N];
void multi(ll a[][4],ll b[][4])
{
memset(tmp,0,sizeof tmp);
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
for(int k=0;k<4;k++)
tmp[i][j]=(tmp[i][j]+a[i][k]*b[k][j])%MOD;
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
a[i][j]=tmp[i][j];
}
char str;
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
while(~scanf("%lld",&n)){
ll a[5][4]={3,3,2,2,2,3,3,2,2,2,3,3,3,2,2,3};
ll b[5][4]={3,3,2,2,2,3,3,2,2,2,3,3,3,2,2,3};
n--;
while(n){
if(n&1){
multi(a,b);
}
multi(b,b);
n/=2;
}
cout<0][0]<<endl;
}
//cout << "Hello world!" << endl;
return 0;
}


 

数论：矩阵快速幂

相关

标签