QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#659028 | #9479. And DNA | ucup-team3586# | AC ✓ | 0ms | 3812kb | C++23 | 1.7kb | 2024-10-19 18:17:21 | 2024-10-19 18:17:21 |
Judging History
answer
//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
const ll mod=998244353;
using matrix=vector<vector<ll>>;
matrix mul(matrix a,matrix b)
{
int n=sz(a);
matrix ret(n,vector<ll>(n));
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
for(int k=0;k<n;k++)
ret[i][k]=(ret[i][k]+a[i][j]*b[j][k])%mod;
return ret;
}
int n,m;
ll dp[33][2];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
ll ways=0;
matrix M(4,vector<ll>(4));
for(int a=0;a<4;a++)
for(int b=0;b<4;b++) if((a&1)==(b>>1)) if(((a&1)+((b&1)&(a>>1)))==1)
M[a][b]=1;
matrix ans(4,vector<ll>(4));
for(int i=0;i<4;i++)
ans[i][i]=1;
while(n)
{
if(n&1) ans=mul(ans,M);
M=mul(M,M);
n>>=1;
}
for(int i=0;i<4;i++)
ways=(ways+ans[i][i])%mod;
dp[0][0]=1;
for(int i=0;i<30;i++)
for(int a=0;a<2;a++)
{
if(a==(m>>i&1))
{
dp[i+1][0]=(dp[i+1][0]+dp[i][a])%mod;
dp[i+1][1]=(dp[i+1][1]+dp[i][a])%mod;
}
else
{
dp[i+1][a]=(dp[i+1][a]+dp[i][a]*ways)%mod;
}
}
cout<<dp[30][0]<<'\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3796kb
input:
3 2
output:
4
result:
ok "4"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3808kb
input:
3 0
output:
1
result:
ok "1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3520kb
input:
100 100
output:
343406454
result:
ok "343406454"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3768kb
input:
686579306 119540831
output:
260602195
result:
ok "260602195"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
26855095 796233790
output:
492736984
result:
ok "492736984"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
295310488 262950628
output:
503008241
result:
ok "503008241"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
239670714 149827706
output:
994702969
result:
ok "994702969"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
790779949 110053353
output:
898252188
result:
ok "898252188"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
726600542 795285932
output:
183726777
result:
ok "183726777"
Test #10:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
957970519 585582861
output:
298814018
result:
ok "298814018"
Test #11:
score: 0
Accepted
time: 0ms
memory: 3536kb
input:
93349859 634036506
output:
110693443
result:
ok "110693443"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3732kb
input:
453035113 34126396
output:
306244220
result:
ok "306244220"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
31994526 100604502
output:
930620701
result:
ok "930620701"
Test #14:
score: 0
Accepted
time: 0ms
memory: 3516kb
input:
234760741 249817734
output:
440195858
result:
ok "440195858"
Test #15:
score: 0
Accepted
time: 0ms
memory: 3472kb
input:
542621111 646412689
output:
207377992
result:
ok "207377992"
Test #16:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
28492783 602632297
output:
65234506
result:
ok "65234506"
Test #17:
score: 0
Accepted
time: 0ms
memory: 3528kb
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: 3604kb
input:
585126464 450455977
output:
91109717
result:
ok "91109717"
Test #20:
score: 0
Accepted
time: 0ms
memory: 3524kb
input:
236696315 482334538
output:
925575199
result:
ok "925575199"
Test #21:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
632719214 298704996
output:
358926097
result:
ok "358926097"
Test #22:
score: 0
Accepted
time: 0ms
memory: 3724kb
input:
869119333 933404114
output:
318501108
result:
ok "318501108"
Test #23:
score: 0
Accepted
time: 0ms
memory: 3524kb
input:
6977994 814763202
output:
585332987
result:
ok "585332987"
Test #24:
score: 0
Accepted
time: 0ms
memory: 3524kb
input:
3 1
output:
3
result:
ok "3"
Test #25:
score: 0
Accepted
time: 0ms
memory: 3596kb
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: 3576kb
input:
4 1
output:
2
result:
ok "2"
Test #28:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
4 1000000000
output:
1755648
result:
ok "1755648"
Test #29:
score: 0
Accepted
time: 0ms
memory: 3476kb
input:
1000000000 0
output:
1
result:
ok "1"
Test #30:
score: 0
Accepted
time: 0ms
memory: 3808kb
input:
1000000000 1
output:
696798313
result:
ok "696798313"
Test #31:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
1000000000 1000000000
output:
703786301
result:
ok "703786301"
Extra Test:
score: 0
Extra Test Passed