QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#764942 | #9479. And DNA | SpadeA261 | AC ✓ | 0ms | 3720kb | C++17 | 2.0kb | 2024-11-20 11:16:48 | 2024-11-20 11:16:49 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
template<class T1,class T2> bool cmax(T1& a,const T2& b){return a<b?a=b,1:0;}
template<class T1,class T2> bool cmin(T1& a,const T2& b){return b<a?a=b,1:0;}
#define fir(i,x,y,...) for(int i(x),##__VA_ARGS__;i<=(y);i++)
#define firr(i,x,y,...) for(int i(x),##__VA_ARGS__;i>=(y);i--)
#define fird(i,x,y,d,...) for(int i(x),##__VA_ARGS__;i<=(y);i+=(d))
#define firrd(i,x,y,d,...) for(int i(x),##__VA_ARGS__;i>=(y);i-=(d))
#define Yes cout<<"Yes\n"
#define No cout<<"No\n"
#define YES cout<<"YES\n"
#define NO cout<<"NO\n"
#define endl "\n"
#define ll long long
#define ull unsigned long long
int T;
bool _mul=0;
int gcd(int x,int y){if(!y) return x;return gcd(y,x%y);}
int power(int b,int p,int mod){int res=1;while(p){if(p&1) res=1ll*res*b%mod;b=1ll*b*b%mod;p>>=1;}return res;}
const int mod=998244353;
int n,m,x;
struct mat
{
int a[3][3];
mat operator*(const mat &x)
{
mat res{};
fir(i,0,2) fir(k,0,2) fir(j,0,2) (res.a[i][j]+=1ll*a[i][k]*x.a[k][j]%mod)%=mod;
return res;
}
mat operator^(int p)
{
mat res{};
mat base{};
fir(i,0,2) res.a[i][i]=1;
fir(i,0,2) fir(j,0,2) base.a[i][j]=a[i][j];
while(p)
{
if(p&1) res=res*base;
base=base*base;
p>>=1;
}
return res;
}
}S;
map<int,int> mp;
int dfs(int now)
{
if(now<=1) return now?x:1;
if(mp.count(now)) return mp[now];
if(now%2==0) return mp[now]=(dfs(now/2)+dfs(now/2-1))%mod;
return mp[now]=1ll*x*dfs(now/2)%mod;
}
void solve()
{
cin>>n>>m;
S.a[0][1]=S.a[0][2]=S.a[1][0]=S.a[2][1]=1;
S=S^n;
x=((S.a[0][0]+S.a[1][1])%mod+S.a[2][2])%mod;
cout<<dfs(m)<<endl;
return;
}
int main()
{
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
cin.tie(nullptr)->sync_with_stdio(false);
if(_mul) cin>>T;
else T=1;
while(T--) solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3644kb
input:
3 2
output:
4
result:
ok "4"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
3 0
output:
1
result:
ok "1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
100 100
output:
343406454
result:
ok "343406454"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
686579306 119540831
output:
260602195
result:
ok "260602195"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
26855095 796233790
output:
492736984
result:
ok "492736984"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3708kb
input:
295310488 262950628
output:
503008241
result:
ok "503008241"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
239670714 149827706
output:
994702969
result:
ok "994702969"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
790779949 110053353
output:
898252188
result:
ok "898252188"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3668kb
input:
726600542 795285932
output:
183726777
result:
ok "183726777"
Test #10:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
957970519 585582861
output:
298814018
result:
ok "298814018"
Test #11:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
93349859 634036506
output:
110693443
result:
ok "110693443"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
453035113 34126396
output:
306244220
result:
ok "306244220"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
31994526 100604502
output:
930620701
result:
ok "930620701"
Test #14:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
234760741 249817734
output:
440195858
result:
ok "440195858"
Test #15:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
542621111 646412689
output:
207377992
result:
ok "207377992"
Test #16:
score: 0
Accepted
time: 0ms
memory: 3664kb
input:
28492783 602632297
output:
65234506
result:
ok "65234506"
Test #17:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
213500301 768820204
output:
540205113
result:
ok "540205113"
Test #18:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
697808101 753041955
output:
93561295
result:
ok "93561295"
Test #19:
score: 0
Accepted
time: 0ms
memory: 3664kb
input:
585126464 450455977
output:
91109717
result:
ok "91109717"
Test #20:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
236696315 482334538
output:
925575199
result:
ok "925575199"
Test #21:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
632719214 298704996
output:
358926097
result:
ok "358926097"
Test #22:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
869119333 933404114
output:
318501108
result:
ok "318501108"
Test #23:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
6977994 814763202
output:
585332987
result:
ok "585332987"
Test #24:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
3 1
output:
3
result:
ok "3"
Test #25:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
3 1000000000
output:
279679226
result:
ok "279679226"
Test #26:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
4 0
output:
1
result:
ok "1"
Test #27:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
4 1
output:
2
result:
ok "2"
Test #28:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
4 1000000000
output:
1755648
result:
ok "1755648"
Test #29:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
1000000000 0
output:
1
result:
ok "1"
Test #30:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
1000000000 1
output:
696798313
result:
ok "696798313"
Test #31:
score: 0
Accepted
time: 0ms
memory: 3720kb
input:
1000000000 1000000000
output:
703786301
result:
ok "703786301"
Extra Test:
score: 0
Extra Test Passed