博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
CF1106F Lunar New Year and a Recursive Sequence
阅读量:5158 次
发布时间:2019-06-13

本文共 1494 字,大约阅读时间需要 4 分钟。

又傻掉了呢

看到连乘显然直接转原根变成线性齐次递推式。
矩阵乘法求一发。
然后分析一下发现是个x^k=m的形式。
按照套路解一下高次方程就好了。
需要用到exgcd和bsgs。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define N 120#define L 110#define eps 1e-7#define inf 1e9+7#define db double#define ll long long#define ldb long doubleusing namespace std;inline ll read(){ char ch=0; ll x=0,flag=1; while(!isdigit(ch)){ch=getchar();if(ch=='-')flag=-1;} while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return x*flag;}const ll g=3;const ll p=998244352;const ll mo=998244353;struct matrix { ll s[N][N]; void clear(){memset(s,0,sizeof(s));}};matrix operator*(matrix a,matrix b){ matrix ans; ans.clear(); for(ll i=0;i<=L;i++) for(ll j=0;j<=L;j++) for(ll k=0;k<=L;k++) ans.s[i][j]=(ans.s[i][j]+(a.s[i][k]*b.s[k][j]%p))%p; return ans;}matrix ksm(matrix x,ll k){ matrix ans; ans.clear(); for(ll i=0;i<=L;i++)ans.s[i][i]=1; while(k) { if(k&1)ans=ans*x; k>>=1; x=x*x; } return ans;}matrix f;ll qpow(ll x,ll k){ ll ans=1; while(k) { if(k&1)ans=ans*x%mo; k>>=1; x=x*x%mo; } return ans;}ll X,Y;ll exgcd(ll a,ll b){ if(!b){X=1,Y=0;return a;} ll d=exgcd(b,a%b); ll t=X;X=Y,Y=t-(a/b)*Y; return d;}map
S;map
::iterator it;ll bsgs(ll a,ll n){ S.clear(); ll x=1,k=1,len=sqrt(mo); for(ll i=0;i
{x,i}); for(ll i=0;i
second); } return 0;}int main(){ ll k=read(); f.clear(); for(ll i=1;i

转载于:https://www.cnblogs.com/Creed-qwq/p/10349300.html

你可能感兴趣的文章
BOM之history对象(转)
查看>>
maven项目正常运行,项目图标打红叉叉解决方法(个人笔记)
查看>>
软件工程(2018)第二次团队作业
查看>>
GoLang执行需要输入密码的命令
查看>>
一款古老的 Scheme 编译器,一台古老的“机器”
查看>>
Centos 配置eth0 提示Device does not seem to be present
查看>>
值类型,引用类型,装箱,拆箱
查看>>
用Eclipse导入JAR的图片详细解说
查看>>
IDEA中Spring boot配置热部署无效问题解决方式(转)
查看>>
Elastix 1.5.2 安装ilbc code步骤
查看>>
知识点查缺补漏贴03:单机最大进程数,线程数和Socket连接数
查看>>
多张图片,限制大小,格式.md
查看>>
类的魔术方法之比较符号
查看>>
【转】IOS开发中图片资源使用png还是jpg格式
查看>>
iOS-获取当前网页的 url 和 title 和 html
查看>>
iOS捕获异常,常用的异常处理方法
查看>>
在Linux下将TPC-H数据导入到MySQL
查看>>
JAVA 日志级别
查看>>
省选模板复习—【字符串】
查看>>
boost any
查看>>