[ARC135] A - Floor, Ceil - Decomposition

[Q] https://atcoder.jp/contests/arc135/tasks/arc135_a

メモ化再帰につきる。

X=11が渡されたら

0) 11の処理
M[11] = dfs(5) * dfs(6)
        ~~~~~~1  ~~~~~~2
1) 5の処理
M[5] = dfs(2) * dfs(3)

M[2] = 2
M[3] = 3

2) 6の処理
M[6] = dfs(3) * dfs(3)
     = M[3] * M[3]
     = 9

メモ帳 M には、
M[2] = 2
M[3] = 3
M[5] = 6
M[6] = 9
M[11] = 54

の5つのデータが入るかもしれない。

実装

map<ll, ll> M; // メモ帖
ll MOD = 998244353;

ll dfs(ll X){
 if (M.count(X)) return M[X]; // もし X の値を処理したことがあるなら、結果を返す
 if (X<5) return X; // 4以下を分割しても増えない
 return M[X] = (dfs(X / 2) * dfs(X / 2 + X % 2) ) % MOD; // Mにメモして、問題文通りの処理
}

int main(){
 cincout();
 
 ll X;
 cin >> X;
 
 cout << dfs(X) << endl;
}

https://atcoder.jp/contests/arc135/submissions/29320695

Q. 問題文通り処理するとTLE
A. 多分O(X)になってる

最大で10^18が入りうる。

1^18 ≒ 2^60

処理すると、
2^60 -> 2^59 * 2^59 // 2で割ったら、2^59にわかれる。
     -> 2^58 * 2^58 * 2^58 * 2^58 // 4要素
     -> 2^57 * 2^3 // 8要素ある
     -> ...
     -> 1 * 2^60

結果 2^60 回処理してることになっていそう。