QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#699053 | #9479. And DNA | wangjingheng | AC ✓ | 1ms | 3752kb | C++20 | 1.8kb | 2024-11-02 00:10:49 | 2024-11-02 00:10:50 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define ll long long
using namespace std;
const int N=3e5+10,mod=998244353,maxn=5;
struct ahaha{
ll a[maxn][maxn]; //一定要用long long存矩阵,否则在过程中会爆掉
ahaha(){
memset(a,0,sizeof a);
}
inline void build(){ //建造单位矩阵
for(int i=1;i<=3;++i)a[i][i]=1;
}
}a;
ahaha operator *(const ahaha &x,const ahaha &y){ //重载运算符
ahaha z;
for(int k=1;k<=3;++k)
for(int i=1;i<=3;++i)
for(int j=1;j<=3;++j)
z.a[i][j]=(z.a[i][j]+x.a[i][k]*y.a[k][j]%mod)%mod;
return z;
}
ll k;
inline void init(){
for(int i=1;i<=3;i++){
for(int j=1;j<=3;j++) a.a[i][j]=0;
}
a.a[1][2]=a.a[1][3]=a.a[2][1]=a.a[3][2]=1;
}
map<int,int> f;
int qpow(int x,int y){
int res=1;
while(y){
if(y&1ll) res=res*x%mod;
x=x*x%mod;
y>>=1ll;
}
return res;
}
void dfs(int x){
if(f[x]) return;
if(x%2==0){
dfs(x/2);dfs(x/2-1);
f[x]=(f[x/2]+f[x/2-1])%mod;
}
else{
dfs(x/2);
f[x]=f[1]*f[x/2]%mod;
}
return;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n,m;cin>>n>>m;
init();
k=n-2;
ahaha ans;ans.build();
do{ //递推快速幂,与普通的递推快速幂无异,但*不能缩写为*=
if(k&1)ans=ans*a;
a=a*a;k>>=1;
}while(k);
int fin=0;
for(int i=1;i<=3;i++){
for(int j=1;j<=3;j++){
fin=(fin+ans.a[i][j])%mod;
}
}
fin=(fin-ans.a[1][2]+mod)%mod;
fin=(fin-ans.a[3][3]+mod)%mod;
fin=(fin-ans.a[2][3]+mod)%mod;
fin=(fin-ans.a[3][1]+mod)%mod;
f[1]=fin;f[0]=1;
dfs(m);
cout<<f[m];
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3600kb
input:
3 2
output:
4
result:
ok "4"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3680kb
input:
3 0
output:
1
result:
ok "1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
100 100
output:
343406454
result:
ok "343406454"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3676kb
input:
686579306 119540831
output:
260602195
result:
ok "260602195"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3752kb
input:
26855095 796233790
output:
492736984
result:
ok "492736984"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
295310488 262950628
output:
503008241
result:
ok "503008241"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3676kb
input:
239670714 149827706
output:
994702969
result:
ok "994702969"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3696kb
input:
790779949 110053353
output:
898252188
result:
ok "898252188"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3680kb
input:
726600542 795285932
output:
183726777
result:
ok "183726777"
Test #10:
score: 0
Accepted
time: 0ms
memory: 3680kb
input:
957970519 585582861
output:
298814018
result:
ok "298814018"
Test #11:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
93349859 634036506
output:
110693443
result:
ok "110693443"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3664kb
input:
453035113 34126396
output:
306244220
result:
ok "306244220"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3700kb
input:
31994526 100604502
output:
930620701
result:
ok "930620701"
Test #14:
score: 0
Accepted
time: 0ms
memory: 3680kb
input:
234760741 249817734
output:
440195858
result:
ok "440195858"
Test #15:
score: 0
Accepted
time: 1ms
memory: 3620kb
input:
542621111 646412689
output:
207377992
result:
ok "207377992"
Test #16:
score: 0
Accepted
time: 0ms
memory: 3680kb
input:
28492783 602632297
output:
65234506
result:
ok "65234506"
Test #17:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
213500301 768820204
output:
540205113
result:
ok "540205113"
Test #18:
score: 0
Accepted
time: 0ms
memory: 3680kb
input:
697808101 753041955
output:
93561295
result:
ok "93561295"
Test #19:
score: 0
Accepted
time: 0ms
memory: 3736kb
input:
585126464 450455977
output:
91109717
result:
ok "91109717"
Test #20:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
236696315 482334538
output:
925575199
result:
ok "925575199"
Test #21:
score: 0
Accepted
time: 0ms
memory: 3680kb
input:
632719214 298704996
output:
358926097
result:
ok "358926097"
Test #22:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
869119333 933404114
output:
318501108
result:
ok "318501108"
Test #23:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
6977994 814763202
output:
585332987
result:
ok "585332987"
Test #24:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
3 1
output:
3
result:
ok "3"
Test #25:
score: 0
Accepted
time: 0ms
memory: 3748kb
input:
3 1000000000
output:
279679226
result:
ok "279679226"
Test #26:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
4 0
output:
1
result:
ok "1"
Test #27:
score: 0
Accepted
time: 0ms
memory: 3732kb
input:
4 1
output:
2
result:
ok "2"
Test #28:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
4 1000000000
output:
1755648
result:
ok "1755648"
Test #29:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
1000000000 0
output:
1
result:
ok "1"
Test #30:
score: 0
Accepted
time: 0ms
memory: 3740kb
input:
1000000000 1
output:
696798313
result:
ok "696798313"
Test #31:
score: 0
Accepted
time: 0ms
memory: 3740kb
input:
1000000000 1000000000
output:
703786301
result:
ok "703786301"
Extra Test:
score: 0
Extra Test Passed