結果

問題 No.3431 popcount & sum (Easy)
コンテスト
ユーザー pengin_2000
提出日時 2026-01-11 16:06:04
言語 C
(gcc 15.2.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 4,914 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,679 ms
コンパイル使用メモリ 44,868 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2026-01-11 16:06:07
合計ジャッジ時間 1,177 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 9
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<stdio.h>
long long int dp[100][2][2][200], cnt[100][2][2][200];
int main()
{
	long long int n;
	scanf("%lld", &n);
	const long long int p = 998244353;
	long long int i, j, k, l;
	for (i = 0; i < 100; i++)
		for (j = 0; j < 2; j++)
			for (k = 0; k < 2; k++)
				for (l = 0; l < 200; l++)
					dp[i][j][k][l] = 0;
	cnt[62][0][0][100] = 1;
	for (l = 61; l >= 0; l--)
	{
		if (((n >> l) & 1) > 0)
		{
			//dp[l+1][0][0][100]
			//1,1
			cnt[l][0][0][100] = 1;
			dp[l][0][0][100] += (dp[l + 1][0][0][100] + ((long long int)(1) << l)) % p;
			dp[l][0][0][100] %= p;
			//1,0
			cnt[l][0][1][101]++;
			cnt[l][0][1][101] %= p;
			dp[l][0][1][101] += dp[l + 1][0][0][100];
			dp[l][0][1][101] %= p;
			//0,0
			cnt[l][1][0][100]++;
			cnt[l][1][0][100] %= p;
			dp[l][1][0][100] += dp[l + 1][0][0][100];
			dp[l][1][0][100] %= p;
			//dp[l+1][0][1][i]
			for (i = 1; i < 199; i++)
			{
				//1,1
				cnt[l][0][1][i] += cnt[l + 1][0][1][i];
				cnt[l][0][1][i] %= p;
				dp[l][0][1][i] += (dp[l + 1][0][1][i] + ((long long int)(1) << l) % p * cnt[l + 1][0][1][i]) % p;
				dp[l][0][1][i] %= p;
				//1,0
				cnt[l][0][1][i + 1] += cnt[l + 1][0][1][i];
				cnt[l][0][1][i + 1] %= p;
				dp[l][0][1][i + 1] += dp[l + 1][0][1][i];
				dp[l][0][1][i + 1] %= p;
				//0,1
				cnt[l][1][1][i-1] += cnt[l + 1][0][1][i];
				cnt[l][1][1][i-1] %= p;
				dp[l][1][1][i - 1] += dp[l + 1][0][1][i];
				dp[l][1][1][i-1] %= p;
				//0,0
				cnt[l][1][1][i] += cnt[l + 1][0][1][i];
				cnt[l][1][1][i] %= p;
				dp[l][1][1][i] += dp[l + 1][0][1][i];
				dp[l][1][1][i] %= p;
			}
			//dp[l+1][1][0][i]
			for (i = 1; i < 199; i++)
			{
				//1,1
				cnt[l][1][0][i] += cnt[l + 1][1][0][i];
				cnt[l][1][0][i] %= p;
				dp[l][1][0][i] += (dp[l + 1][1][0][i] + ((long long int)(1) << l) % p * cnt[l + 1][1][0][i]) % p;
				dp[l][1][0][i] %= p;
				//1,0
				cnt[l][1][1][i + 1] += cnt[l + 1][1][0][i];
				cnt[l][1][1][i + 1] %= p;
				dp[l][1][1][i + 1] += dp[l + 1][1][0][i];
				dp[l][1][1][i + 1] %= p;
				//0,0
				cnt[l][1][0][i] += cnt[l + 1][1][0][i];
				cnt[l][1][0][i] %= p;
				dp[l][1][0][i] += dp[l + 1][1][0][i];
				dp[l][1][0][i] %= p;
			}
			//dp[l+1][1][1][i]
			for (i = 1; i < 199; i++)
			{
				//1,1
				cnt[l][1][1][i] += cnt[l + 1][1][1][i];
				cnt[l][1][1][i] %= p;
				dp[l][1][1][i] += (dp[l + 1][1][1][i] + ((long long int)(1) << l) % p * cnt[l + 1][1][1][i]) % p;
				dp[l][1][1][i] %= p;
				//1,0
				cnt[l][1][1][i+1] += cnt[l + 1][1][1][i];
				cnt[l][1][1][i+1] %= p;
				dp[l][1][1][i + 1] += dp[l + 1][1][1][i];
				dp[l][1][1][i+1] %= p;
				//0,1
				cnt[l][1][1][i - 1] += cnt[l + 1][1][1][i];
				cnt[l][1][1][i - 1] %= p;
				dp[l][1][1][i - 1] += dp[l + 1][1][1][i];
				dp[l][1][1][i - 1] %= p;
				//0,0
				cnt[l][1][1][i] += cnt[l + 1][1][1][i];
				cnt[l][1][1][i] %= p;
				dp[l][1][1][i] += dp[l + 1][1][1][i];
				dp[l][1][1][i] %= p;
			}
		}
		else
		{
			//dp[l+1][0][0][100]
			//0,0
			cnt[l][0][0][100]++;
			cnt[l][0][0][100] %= p;
			dp[l][0][0][100] += dp[l + 1][0][0][100];
			dp[l][0][0][100] %= p;
			//dp[l+1][0][1][i]
			for (i = 1; i < 199; i++)
			{
				//0,1
				cnt[l][0][1][i - 1] += cnt[l + 1][0][1][i];
				cnt[l][0][1][i - 1] %= p;
				dp[l][0][1][i - 1] += dp[l + 1][0][1][i];
				dp[l][0][1][i - 1] %= p;
				//0,0
				cnt[l][0][1][i] += cnt[l + 1][0][1][i];
				cnt[l][0][1][i] %= p;
				dp[l][0][1][i] += dp[l + 1][0][1][i];
				dp[l][0][1][i] %= p;
			}
			//dp[l+1][1][0][i]
			for (i = 1; i < 199; i++)
			{
				//1,1
				cnt[l][1][0][i] += cnt[l + 1][1][0][i];
				cnt[l][1][0][i] %= p;
				dp[l][1][0][i] += (dp[l + 1][1][0][i] + ((long long int)(1) << l) % p * cnt[l + 1][1][0][i]) % p;
				dp[l][1][0][i] %= p;
				//1,0
				cnt[l][1][1][i + 1] += cnt[l + 1][1][0][i];
				cnt[l][1][1][i + 1] %= p;
				dp[l][1][1][i + 1] += dp[l + 1][1][0][i];
				dp[l][1][1][i + 1] %= p;
				//0,0
				cnt[l][1][0][i] += cnt[l + 1][1][0][i];
				cnt[l][1][0][i] %= p;
				dp[l][1][0][i] += dp[l + 1][1][0][i];
				dp[l][1][0][i] %= p;
			}
			//dp[l+1][1][1][i]
			for (i = 1; i < 199; i++)
			{
				//1,1
				cnt[l][1][1][i] += cnt[l + 1][1][1][i];
				cnt[l][1][1][i] %= p;
				dp[l][1][1][i] += (dp[l + 1][1][1][i] + ((long long int)(1) << l) % p * cnt[l + 1][1][1][i]) % p;
				dp[l][1][1][i] %= p;
				//1,0
				cnt[l][1][1][i + 1] += cnt[l + 1][1][1][i];
				cnt[l][1][1][i + 1] %= p;
				dp[l][1][1][i + 1] += dp[l + 1][1][1][i];
				dp[l][1][1][i + 1] %= p;
				//0,1
				cnt[l][1][1][i - 1] += cnt[l + 1][1][1][i];
				cnt[l][1][1][i - 1] %= p;
				dp[l][1][1][i - 1] += dp[l + 1][1][1][i];
				dp[l][1][1][i - 1] %= p;
				//0,0
				cnt[l][1][1][i] += cnt[l + 1][1][1][i];
				cnt[l][1][1][i] %= p;
				dp[l][1][1][i] += dp[l + 1][1][1][i];
				dp[l][1][1][i] %= p;
			}
		}
	}
	long long int ans = 0;
	l = 0;
	k = 100;
	for (i = 0; i < 2; i++)
		for (j = 0; j < 2; j++)
			ans = (ans + dp[l][i][j][k]) % p;
	printf("%lld\n", ans);
	return 0;
}
0