字节跳动-文远知行杯 广东工业大学第十四届程序设计竞赛（A、B、C、G、J）

• A题目:签到题目
• • B题目(矩阵面积)
  • C题目：简单思维题目pta原题
  • • G题目：公式题目
    • J题目：矩阵快速幂

思路：直接输出4个1

思路：可以从图中看出它所滚过的面积是大矩阵减小矩阵。大矩阵是最后的矩阵，小矩阵是还没有开始滚的位置。
代码：

#include
using namespace std;
typedef long long int ll;
const ll N=50100;
const ll mod=192600817;
ll a[N];
ll sum[N];
int main(){
	int n;
	a[0]=1;
	a[1]=1;
	for(int i=2;i<=N;i++){//预处理
		a[i]=(a[i-1]+a[i-2]+mod)%mod;
	}
	while(scanf("%d",&n)!=EOF){
		while(n--){
			ll q,b,c,d,s=0;
			scanf("%lld%lld%lld%lld",&q,&b,&c,&d);
			ll k=c*4+d;
			ll p=q*4+b;
			if(p 
C题目：简单思维题目pta原题 
思路：做下预处理，判断一个数是不是鸽子，只需要判断会不会重复出现一个数（位数平方之和）。
 代码：
 
#include
using namespace std;
typedef long long int ll;
const ll maxn=1e6+10;
ll a[maxn];
map mp;
ll k=1;
int main(){
	a[1]=1;
	for(int i=2;;i++){
		ll sum=i;
		mp.clear();
		while(!mp[sum]){
			ll s=sum;
            mp[sum]=1;
			ll s1=0;
			while(s){
				s1+=(s%10)*(s%10);
				s/=10;
			}
			sum=s1;
			if(s1==1){
				k++;
				a[k]=i;
				break;
			}
		}
		if(k==150000){
			break;
		}
	}
	ll t,k;
	scanf("%lld",&t);
	while(t--){
		scanf("%lld",&k);
		printf("%lldn",a[k]);
	}
}
 
G题目：公式题目 
思路：10的18次方的数据范围，一定是有比较取巧的方法。这个题目是能推出一个公式，具体可以看下面链接
 链接：https://www.cnblogs.com/luowentao/p/10545142.html
 代码：
 
#include 
#define ll long long
using namespace std;
const int N=1e6+100;
const ll mod=1e9+7;
ll pw(ll a,ll b,ll mod)
{
	ll res=1;
	while(b)
	{
		if(b%2) res=(res*a)%mod;
		a=(a*a)%mod;
		b/=2;
	}
	return res;
}
int main()
{
	ll n;
	while(~scanf("%lld",&n))
	{
		ll ans;
		ans=((n-1)%mod*pw(2,n,mod)%mod+1)%mod;
		cout< 
J题目：矩阵快速幂 
思路：可以有公式推出，这是一个公式递推的题目。数据较大
 
资料链接：传送门
 
 
代码：
 
#include
using namespace std;
typedef long long int ll;
const ll maxn=3010;
const ll N=3005;
const ll mod=123456789;
ll n;
struct martix{
    ll a[11][11];
    ll r,c;
    martix(int n,int m):r(n),c(m){
        memset(a,0,sizeof(a));
    }
    ll* operator[](int x){//定义运算符
        return a[x];
    }
    friend martix operator*(martix A,martix B){//定义乘法
        martix C(A.r,B.c);
        for(int i=1;i<=A.r;i++){
            for(int j=1;j<=B.c;j++){
                for(int k=1;k<=A.c;k++){
                    C[i][j]+=(A[i][k]*B[k][j]);
                    C[i][j]+=mod;
                    C[i][j]%=mod;
                }
            }
        }
        return C;
    }
};
martix qpow(martix A,ll m){
    martix ans(A.r,A.c);
    for(int i=1;i<=A.r;i++)ans.a[i][i]=1;
    while(m){
        if(m&1)ans=ans*A;
        A=A*A;
        m>>=1;
    }
    return ans;
}
int main(){
    ll t,n;
    cin>>t;
    while(t--){
        cin>>n;
        martix A(6,6);
        A[1][1]=1;
        A[1][2]=2;
        A[1][3]=1;
        A[1][4]=3;
        A[1][5]=3;
        A[1][6]=1;
        A[2][1]=1;
        A[3][3]=1;
        A[4][3]=1;
        A[4][4]=1;
        A[5][3]=1;
        A[5][4]=2;
        A[5][5]=1;
        A[6][3]=1;
        A[6][4]=3;
        A[6][5]=3;
        A[6][6]=1;
        martix X2(6,1);
        X2[1][1]=2;
        X2[2][1]=1;
        X2[3][1]=1;
        X2[4][1]=2;
        X2[5][1]=4;
        X2[6][1]=8;

        martix Xn=qpow(A,n-2)*X2;
        printf("%lldn",Xn[1][1]);
    }
    return 0;
}