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 <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=+;

const int MOD=;

const double PI = acos(-1.0);

const double EXP = 1E-;

const int INF = 0x3f3f3f3f;

ll t,n,m,k,q,ans;

ll a[];

char str;

int main()

{

#ifdef DEBUG

freopen("input.in", "r", stdin);

//freopen("output.out", "w", stdout);

#endif

while(~scanf("%lld",&n)){

memset(a,,sizeof(a));

a[]=;

a[]=;

a[]=;

a[]=;

for(int i=;i<=n;i++){

int x=a[],y=a[],z=a[],t=a[];

a[]=(x*+y*+z*+t*)%MOD;

a[]=(x*+y*+z*+t*)%MOD;

a[]=(x*+y*+z*+t*)%MOD;

a[]=(x*+y*+z*+t*)%MOD;

}

cout<<a[]<<endl;

}

//cout << "Hello world!" << endl;

return ;

}

很明显肯定会超时。

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

矩阵快速幂

#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=;

const int MOD=;

const double PI = acos(-1.0);

const double EXP = 1E-;

const int INF = 0x3f3f3f3f;

ll t,n,m,k,q,ans;

ll a[][]={,,,,,,,,,,,,,,,};

ll b[][]={,,,,,,,,,,,,,,,};

int tmp[N][N];

void multi(ll a[][],ll b[][])

{

memset(tmp,,sizeof tmp);

for(int i=;i<;i++)

for(int j=;j<;j++)

for(int k=;k<;k++)

tmp[i][j]=(tmp[i][j]+a[i][k]*b[k][j])%MOD;

for(int i=;i<;i++)

for(int j=;j<;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[][]={,,,,,,,,,,,,,,,};

ll b[][]={,,,,,,,,,,,,,,,};

n--;

while(n){

if(n&){

multi(a,b);

}

multi(b,b);

n/=;

}

cout<<a[][]<<endl;

}

//cout << "Hello world!" << endl;

return ;

}

巴特西

The Digits String

最新文章

热门文章