結果

問題 No.3432 popcount & sum (Hard)
コンテスト
ユーザー <bits/stdc++.h>
提出日時 2026-01-11 14:33:35
言語 C#
(.NET 10.0.101)
結果
AC  
実行時間 86 ms / 2,000 ms
コード長 1,314 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 14,531 ms
コンパイル使用メモリ 166,900 KB
実行使用メモリ 36,140 KB
最終ジャッジ日時 2026-01-11 14:33:52
合計ジャッジ時間 14,447 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 16
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (120 ミリ秒)。
  main -> /home/judge/data/code/bin/Release/net10.0/main.dll
  main -> /home/judge/data/code/bin/Release/net10.0/publish/

ソースコード

diff #
raw source code 

#nullable enable

#region
var (_input, _iter) = (Array.Empty<string>(), 0);
T I<T>() where T : IParsable<T>
{
    while (_iter >= _input.Length) (_input, _iter) = (Console.ReadLine()!.Trim().Split(' '), 0);
    return T.Parse(_input[_iter++], null);
}
#endregion

const int Mod = 998244353;
var n = I<long>();

var f = new Dictionary<(long, long, int, int), (long, long)>();
(long, long) F(long za, long zb, int zd, int comp)
{
    if (za == 0 && zb == 0)
    {
        if (zd != 0) return (0, 0);
        if (comp < 0) return (0, 0);
        return (0, 1);
    }
    var key = (za, zb, zd, comp);
    if (f.TryGetValue(key, out var cv)) return cv;

    var rv = 0L;
    var rc = 0L;

    {
        var (v00, c00) = F(za >> 1, zb >> 1, zd, comp);
        rv += v00 * 2;
        rc += c00;
    }
    if (za > 0)
    {
        var (v10, c10) = F((za - 1) >> 1, zb >> 1, zd - 1, -1);
        rv += v10 * 2;
        rc += c10;
    }
    if (zb > 0)
    {
        var (v01, c01) = F(za >> 1, (zb - 1) >> 1, zd + 1, 1);
        rv += v01 * 2;
        rc += c01;
    }
    if (za > 0 && zb > 0)
    {
        var (v11, c11) = F((za - 1) >> 1, (zb - 1) >> 1, zd, comp);
        rv += v11 * 2 + c11;
        rc += c11;
    }
    return f[key] = (rv % Mod, rc % Mod);
}
var ans = F(n, n, 0, 0).Item1;
Console.WriteLine(ans);
0