竞赛讨论区 > 【每日一题】12月15日题目精讲
头像
王清楚
编辑于 2020-12-15 10:56
+ 关注

【每日一题】12月15日题目精讲

题号 NC21884
名称 函数的魔法
来源 牛客练习赛35
戳我进入往期每日一题汇总贴~
往期每日一题二期题单

图片说明

如果你在题库做题时遇到了喜欢的题目,欢迎推荐给邓老师~ 点击查看详情
每日一题QQ群:659028468

题解

假设我们用一个邻接矩阵来表示计算步骤, 连接一条有向边代表 可以经过一次计算得到 ,也就是说,对于 以及 都连接一条有向边。这样就得到了一个 233*233 的邻接矩阵。
对于一个邻接矩阵而言,矩阵中的元素都是用0,1来表示是否联通的,或者说,代表有没有方法从走到。那么,就是表示从 走到 再走到 是否可行。可以发现, 其实就是统计用2步从 走到 的方法总数。
因此,可以预处理出 、…… 这些所有的邻接矩阵(很明显,最多计算232次就足够了)。之后每次询问的时候,复杂度在矩阵中遍历就可以了。
注意要特判两种情况:①a=b的时候,无论怎样直接输出0即可。②除第一种情况以外, 时显然无解,输出-1。
之后询问的时候可以用 在预处理得到的233个邻接矩阵中进行询问。
参考代码:

#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
struct Matrix{
    int a[253][253];
};

long long f(long long x){
    return x*x*(x+1)%233;
}
long long g(long long x){
    return x*x*(x-1)%233;
}
Matrix f(Matrix a)
{
    int i,j,k;
    Matrix tmp;
    for(i=0;i<233;++i)
    {
        for(j=0;j<233;j++)
            if(a.a[i][j]==1)
        {
            tmp.a[i][f(j)]=1;
            tmp.a[i][g(j)]=1;
        }
    }
    return tmp;
}
  Matrix m[253];
int main()
{
    int i;
    for(i=0;i<233;i++)m[0].a[i][i]=1;
    for(i=1;i<=233;i++){
        m[i]=f(m[i-1]);
    }
    int t;
    cin>>t;
    while(t--){
        long long a,b;
        cin>>a>>b;
        if(a==b)cout<<"0"<<endl;
        else if(b>=233)cout<<"-1"<<endl;
        else{
            a%=233;
            for(i=1;i<=233;i++){
                if(m[i].a[a][b]==1)break;
            }
            if(i>233)cout<<-1<<endl;
            else cout<<i<<endl;
        }
    }
}

欢迎各位大佬来做题写题解,也欢迎大家踊跃在当日讨论贴中提问!

活动奖励:

在牛客博客中写出题解,并回复地址
审核通过可获得(依据题目难度和题解的内容而定)

本道题目12月22日中午12:00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

  1. 如何开通牛客博客:https://www.nowcoder.com/discuss/202952
  2. 如何使用博客搬家功能:进入博客--->设置--->底部博客搬家
  3. 如果你对牛客博客有任何意见或建议:牛客博客意见反馈专贴

全部评论

(7) 回帖
加载中...
话题 回帖

本文相关内容

等你来战

查看全部

热门推荐