QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#767833 | #9479. And DNA | acwing_gza | AC ✓ | 0ms | 3764kb | C++14 | 2.2kb | 2024-11-20 22:18:29 | 2024-11-20 22:18:30 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
namespace gza{
#define int long long
#define pb push_back
#define MT int TTT=R;while(TTT--)
#define pc putchar
#define R read()
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define rep(i,a,b) for(int i=a;i>=b;i--)
#define m1(a,b) memset(a,b,sizeof a)
namespace IO
{
inline int read()
{
int x=0;
char ch=getchar();
bool f=0;
while(!isdigit(ch)){if(ch=='-') f=1;ch=getchar();}
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f) x=-x;
return x;
}
template<typename ans> inline void write(ans x)
{
if(x<0) pc('-'),x=-x;
if(x>9) write(x/10);
pc(x%10+'0');
}
};
namespace math
{
inline int gcd(int a,int b)
{
int az=__builtin_ctz(a),bz=__builtin_ctz(b),z=(az>bz)?bz:az,t;
b>>=bz;
while(a) a>>=az,t=a-b,b=a,az=__builtin_ctz(t<0?-t:t),a=t<0?-t:t;
return b<<z;
}
inline int qmi(int a,int b,int p)
{
int res=1;
while(b)
{
if(b&1) res=res*a%p;
a=a*a%p;
b>>=1;
}
return res;
}
const int MAXN=2e6+10;
int my_fac[MAXN],my_inv[MAXN];
void init_binom(int mod)
{
my_fac[0]=1;fo(i,1,min(MAXN,mod)-1) my_fac[i]=my_fac[i-1]*i%mod;
my_inv[min(MAXN,mod)-1]=qmi(my_fac[min(MAXN,mod)-1],mod-2,mod);rep(i,min(MAXN,mod)-2,0) my_inv[i]=my_inv[i+1]*(i+1)%mod;
}
int binom(int a,int b,int mod)
{
if(a<b) return 0;
return my_fac[a]*my_inv[b]%mod*my_inv[a-b]%mod;
}
};
using namespace IO;
using namespace math;
typedef array<array<int,3>,3> Mat;
const int mod=998244353;
Mat operator *(const Mat &u,const Mat &v)
{
Mat w{0,0,0,0,0,0,0,0,0};
fo(i,0,2) fo(k,0,2) fo(j,0,2) w[i][j]=(w[i][j]+u[i][k]*v[k][j])%mod;
return w;
}
int n,m;
Mat base{1,0,0,0,1,0,0,0,1},ans{0,1,1,1,0,0,0,1,0};
unordered_map<int,int> dp;
int tt;
int f(int x)
{
if(x<=1) return x?tt:1;
if(dp.count(x)) return dp[x];
if(x&1) return dp[x]=tt*f(x/2)%mod;
return dp[x]=(f(x/2)+f(x/2-1))%mod;
}
void main(){
n=R,m=R;
for(int k=n;k;k>>=1,ans=ans*ans) if(k&1) base=base*ans;
tt=(base[0][0]+base[1][1]+base[2][2])%mod;
write(f(m)),puts("");
}
}
signed main(){
gza::main();
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3480kb
input:
3 2
output:
4
result:
ok "4"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3472kb
input:
3 0
output:
1
result:
ok "1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3484kb
input:
100 100
output:
343406454
result:
ok "343406454"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3696kb
input:
686579306 119540831
output:
260602195
result:
ok "260602195"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3448kb
input:
26855095 796233790
output:
492736984
result:
ok "492736984"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
295310488 262950628
output:
503008241
result:
ok "503008241"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
239670714 149827706
output:
994702969
result:
ok "994702969"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
790779949 110053353
output:
898252188
result:
ok "898252188"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3476kb
input:
726600542 795285932
output:
183726777
result:
ok "183726777"
Test #10:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
957970519 585582861
output:
298814018
result:
ok "298814018"
Test #11:
score: 0
Accepted
time: 0ms
memory: 3504kb
input:
93349859 634036506
output:
110693443
result:
ok "110693443"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3448kb
input:
453035113 34126396
output:
306244220
result:
ok "306244220"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3540kb
input:
31994526 100604502
output:
930620701
result:
ok "930620701"
Test #14:
score: 0
Accepted
time: 0ms
memory: 3448kb
input:
234760741 249817734
output:
440195858
result:
ok "440195858"
Test #15:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
542621111 646412689
output:
207377992
result:
ok "207377992"
Test #16:
score: 0
Accepted
time: 0ms
memory: 3444kb
input:
28492783 602632297
output:
65234506
result:
ok "65234506"
Test #17:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
213500301 768820204
output:
540205113
result:
ok "540205113"
Test #18:
score: 0
Accepted
time: 0ms
memory: 3492kb
input:
697808101 753041955
output:
93561295
result:
ok "93561295"
Test #19:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
585126464 450455977
output:
91109717
result:
ok "91109717"
Test #20:
score: 0
Accepted
time: 0ms
memory: 3760kb
input:
236696315 482334538
output:
925575199
result:
ok "925575199"
Test #21:
score: 0
Accepted
time: 0ms
memory: 3748kb
input:
632719214 298704996
output:
358926097
result:
ok "358926097"
Test #22:
score: 0
Accepted
time: 0ms
memory: 3472kb
input:
869119333 933404114
output:
318501108
result:
ok "318501108"
Test #23:
score: 0
Accepted
time: 0ms
memory: 3480kb
input:
6977994 814763202
output:
585332987
result:
ok "585332987"
Test #24:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
3 1
output:
3
result:
ok "3"
Test #25:
score: 0
Accepted
time: 0ms
memory: 3540kb
input:
3 1000000000
output:
279679226
result:
ok "279679226"
Test #26:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
4 0
output:
1
result:
ok "1"
Test #27:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
4 1
output:
2
result:
ok "2"
Test #28:
score: 0
Accepted
time: 0ms
memory: 3452kb
input:
4 1000000000
output:
1755648
result:
ok "1755648"
Test #29:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
1000000000 0
output:
1
result:
ok "1"
Test #30:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
1000000000 1
output:
696798313
result:
ok "696798313"
Test #31:
score: 0
Accepted
time: 0ms
memory: 3748kb
input:
1000000000 1000000000
output:
703786301
result:
ok "703786301"
Extra Test:
score: 0
Extra Test Passed