(cache)Submission #65865802 - Panasonic Programming Contest 2025（AtCoder Beginner Contest 406）

Contest Duration: 2025-05-17(Sat) 21:00 - 2025-05-17(Sat) 22:40 (local time) (100 minutes) Back to Home

Submission #65865802

Source Code Expand

Copy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 998244353;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        unsigned long long N;
        int K;
        cin >> N >> K;
        vector<int> bits;
        for (int i = 63; i >= 0; --i) {
            bits.push_back((N >> i) & 1ULL);
        }
        int L = bits.size();
        vector<array<pair<long long,long long>,2>> dp(K+1);
        vector<array<pair<long long,long long>,2>> ndp(K+1);
        for (int c = 0; c <= K; ++c) dp[c][0] = dp[c][1] = {0,0};
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 998244353;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        unsigned long long N;
        int K;
        cin >> N >> K;
        vector<int> bits;
        for (int i = 63; i >= 0; --i) {
            bits.push_back((N >> i) & 1ULL);
        }
        int L = bits.size();
        vector<array<pair<long long,long long>,2>> dp(K+1);
        vector<array<pair<long long,long long>,2>> ndp(K+1);
        for (int c = 0; c <= K; ++c) dp[c][0] = dp[c][1] = {0,0};
        dp[0][1] = {1, 0};

        for (int i = 0; i < L; ++i) {
            unsigned long long bitval = (1ULL << (63 - i)) % MOD;
            for (int c = 0; c <= K; ++c) 
                ndp[c][0] = ndp[c][1] = make_pair(0LL, 0LL);

            for (int c = 0; c <= K; ++c) {
                for (int t = 0; t < 2; ++t) {
                    auto [cnt, sum] = dp[c][t];
                    if (!cnt) continue;
                    for (int b = 0; b <= 1; ++b) {
                        if (t == 1 && b > bits[i]) continue;
                        int nt = (t == 1 && b == bits[i]) ? 1 : 0;
                        int nc = c + b;
                        if (nc > K) continue;
                        long long ncnt = cnt;
                        long long nsum = (sum + (b ? (bitval * cnt) % MOD : 0)) % MOD;
                        auto &cell = ndp[nc][nt];
                        cell.first  = (cell.first  + ncnt) % MOD;
                        cell.second = (cell.second + nsum) % MOD;
                    }
                }
            }
            swap(dp, ndp);
        }
        long long ans = (dp[K][0].second + dp[K][1].second) % MOD;
        cout << ans << "\n";
    }
    return 0;
}

Submission Info

Submission Time	2025-05-17 21:11:30
Task	E - Popcount Sum 3
User	OYU__0YU
Language	C++ 20 (gcc 12.2)
Score	450
Code Size	1850 Byte
Status	AC
Exec Time	2 ms
Memory	3480 KiB

Judge Result

Set Name

Sample

All

Score / Max Score

0 / 0

450 / 450

Status

× 1

× 34

Set Name	Test Cases
Sample	example_00.txt
All	example_00.txt, hand_00.txt, hand_01.txt, hand_02.txt, random_00.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, random_23.txt, random_24.txt, random_25.txt, random_26.txt, random_27.txt, random_28.txt, random_29.txt

Case Name	Status	Exec Time	Memory
example_00.txt	AC	1 ms	3340 KiB
hand_00.txt	AC	2 ms	3268 KiB
hand_01.txt	AC	1 ms	3300 KiB
hand_02.txt	AC	1 ms	3364 KiB
random_00.txt	AC	2 ms	3300 KiB
random_01.txt	AC	2 ms	3396 KiB
random_02.txt	AC	2 ms	3368 KiB
random_03.txt	AC	2 ms	3480 KiB
random_04.txt	AC	2 ms	3284 KiB
random_05.txt	AC	2 ms	3340 KiB
random_06.txt	AC	2 ms	3268 KiB
random_07.txt	AC	2 ms	3276 KiB
random_08.txt	AC	2 ms	3352 KiB
random_09.txt	AC	2 ms	3256 KiB
random_10.txt	AC	2 ms	3328 KiB
random_11.txt	AC	2 ms	3476 KiB
random_12.txt	AC	2 ms	3408 KiB
random_13.txt	AC	2 ms	3384 KiB
random_14.txt	AC	2 ms	3264 KiB
random_15.txt	AC	2 ms	3368 KiB
random_16.txt	AC	2 ms	3340 KiB
random_17.txt	AC	2 ms	3356 KiB
random_18.txt	AC	2 ms	3268 KiB
random_19.txt	AC	2 ms	3256 KiB
random_20.txt	AC	2 ms	3348 KiB
random_21.txt	AC	2 ms	3348 KiB
random_22.txt	AC	2 ms	3380 KiB
random_23.txt	AC	2 ms	3348 KiB
random_24.txt	AC	2 ms	3300 KiB
random_25.txt	AC	2 ms	3292 KiB
random_26.txt	AC	2 ms	3340 KiB
random_27.txt	AC	2 ms	3340 KiB
random_28.txt	AC	2 ms	3480 KiB
random_29.txt	AC	2 ms	3416 KiB