Submission #18,691

2025-10-30 22:54:54

cpp17

Accepted 40/40

1ms

508 KiB

#include <iostream>
#include <unordered_map>
using namespace std;

const int mod=20210108;
unordered_map<int,int> d={{0,0},{1,0},{2,2},{3,2},{4,4},{5,8}};

int f(int n){
  if(d.find(n)!=d.end()) return d[n];
  if(n%2==0){
    int cur=(1LL*f(n/2)*f(n/2)+2LL*f(n/2-1)*f(n/2-1)+4LL*f(n/2-2)*f(n/2-1))%mod;
    d[n]=cur;
    return cur;
  }
  int cur=(1LL*f(n/2)*f(n/2+1)+2LL*f(n/2)*f(n/2-1)+2LL*f(n/2-1)*f(n/2-1)+2LL*f(n/2-2)*f(n/2))%mod;
  d[n]=cur;
  return cur;
}

int main() {
  int N;
  cin>>N;
  cout<<f(N)<<"\n";
  return 0;
}

	Sum	Test	Verdict		Time	Memory
base	40/40
		1	Accepted	0/0	1ms	316 KiB
		2	Accepted	0/0	1ms	316 KiB
		3	Accepted	2/2	1ms	316 KiB
		4	Accepted	2/2	1ms	316 KiB
		5	Accepted	3/3	1ms	316 KiB
		6	Accepted	3/3	1ms	316 KiB
		7	Accepted	3/3	1ms	320 KiB
		8	Accepted	3/3	1ms	316 KiB
		9	Accepted	3/3	1ms	316 KiB
		10	Accepted	3/3	1ms	508 KiB
		11	Accepted	3/3	1ms	404 KiB
		12	Accepted	3/3	1ms	316 KiB
		13	Accepted	4/4	1ms	316 KiB
		14	Accepted	4/4	1ms	412 KiB
		15	Accepted	2/2	1ms	316 KiB
		16	Accepted	2/2	1ms	316 KiB