問題一覧 > 通常問題

No.3431 popcount & sum (Easy)

レベル : / AI推定難易度 : 137 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 80
作問者 : まみめ / テスター : harel hirayuu_yc syndrome kidodesu 👑 ArcAki 👑 qand rogi52 Eku
お気に入りにしたユーザー ProblemId : 12958 / 自分の提出
問題文最終更新日: 2026-01-12 12:56:58
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest YNUCPC Contest 2 (順位表) の他の問題:

※This problem is popcount & sum (Hard) with different constraints.

Problem Statement

For a non-negative integer $k$, let $p(k)$ be "the number of $1$s when $k$ is written in base $2$".
Also, define the function $f(a,b)$ as follows.

$$ f(a,b) = \left\{ \begin{array}{cc} a\ \& \ b & (p(a) = p(b))\\ 0 & (\text{otherwise}) \end{array} \right. $$

Here, $a\ \& \ b$ denotes the $\text{bitwise AND}$ of $a$ and $b$.
$(\text{e.g. } 3\ \& \ 5 = 1,$ in binary notation: $\ 001_{(2)}\ \& \ 101_{(2)} = 001_{(2)})$

Given an integer $n$, find the value of

$$\sum_{a=0}^{n}\sum_{b=a}^{n}f(a,b)$$

modulo $998244353$.

Constraints

  • $0 \leq n \leq 2×10^{3}$
  • The input is an integer.

Input

The input is given from standard input in the following format.

$n$

Output

Output the answer as an integer.

Sample

Sample 1
Input
3
Output
6
Sample 2
Input
15
Output
210
Sample 3
Input
2000
Output
181076134

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。