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時，還是根據前面的余數分布決定接下來可以填什么數。

暴力遞推

/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #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 DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endifwhile(~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<<a[0]<<endl;}//cout << "Hello world!" << endl;return 0; }

很明顯肯定會超時。

a數組和遞推a數組的系數可以構成同一個方矩陣，那么可以通過矩陣快速冪減少時間復雜度。所求的答案就是方陣a的n-1次冪中的a[]0[0];

矩陣快速冪

參考文章：https://blog.csdn.net/weixin_43272781/article/details/85939539

/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #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 DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endifwhile(~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<<a[0][0]<<endl;}//cout << "Hello world!" << endl;return 0; }

?

總結

以上是生活随笔為你收集整理的The Digits String的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。