C++ の動作確認をしてみた（６６６）

C++の練習を兼ねて, AtCoder Beginner Contest 147 の問題D (Xor Sum 4) を解いてみた.

■感想.
1. 問題Dは, 方針を絞り込めたので, AC版に到達できたと思う.
2. 問題D は, 過去問 AtCoder Regular Contest 135 の問題C (XOR to All) に似ていると感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト AtCoder Beginner Contest 147 解説の各リンクをご覧下さい.

■C++版プログラム(問題D／AC版).

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
const LL MOD = 1e9 + 7;
LL a[303030], aCum[303030][61][2];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N){
        scanf("%lld", &a[i]);
        rep(j, 61){
            rep(k, 2) aCum[i + 1][j][k] = aCum[i][j][k];
            if((a[i] >> j) & 1) aCum[i + 1][j][1]++;
            else                aCum[i + 1][j][0]++;
        }
    }
    
    // 2. 集計.
    LL ans = 0;
    rep(i, N){
        rep(j, 61){
            // a[i] の j桁目.
            int d = (a[i] >> j) & 1;
            
            // 1 の とき.
            if(d){
                ans += (aCum[N][j][0] - aCum[i + 1][j][0]) * ((1LL << j) % MOD);
                ans %= MOD;
            }
            
            // 0 の とき.
            if(!d){
                ans += (aCum[N][j][1] - aCum[i + 1][j][1]) * ((1LL << j) % MOD);
                ans %= MOD;
            }
        }
    }
    
    // 3. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

#define repex(i, a, b, c) for(int i = a; i < b; i += c)

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

#define repr(i, a, b) for(int i = a; i >= b; i--)

const LL MOD = 1e9 + 7;

LL a[303030], aCum[303030][61][2];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N){

scanf("%lld", &a[i]);

rep(j, 61){

rep(k, 2) aCum[i + 1][j][k] = aCum[i][j][k];

if((a[i] >> j) & 1) aCum[i + 1][j][1]++;

else aCum[i + 1][j][0]++;

}

// 2. 集計.

LL ans = 0;

rep(i, N){

rep(j, 61){

// a[i] の j桁目.

int d = (a[i] >> j) & 1;

// 1 のとき.

if(d){

ans += (aCum[N][j][0] - aCum[i + 1][j][0]) * ((1LL << j) % MOD);

ans %= MOD;

}

// 0 のとき.

if(!d){

ans += (aCum[N][j][1] - aCum[i + 1][j][1]) * ((1LL << j) % MOD);

ans %= MOD;

}

// 3. 出力.

printf("%lld\n", ans);

return 0;

}

[入力例]
3
1 2 3

[出力例]
6
※AtCoderテストケースより

[入力例]
10
3 1 4 1 5 9 2 6 5 3

[出力例]
237
※AtCoderテストケースより

[入力例]
10
3 14 159 2653 58979 323846 2643383 27950288 419716939 9375105820

[出力例]
103715602
※AtCoderテストケースより

[入力例]
7
1 2 3 4 5 6 7

[出力例]
84

[入力例]
12
95 88 5 63 67 35 67 2 31 39 0 66

[出力例]
4098

[入力例]
120
7728 7084 5138 10586 3785 8265 10064 9492 9517 6355 1229 8848 11106 9216 10861 6522 3376 7719 6997 10628 7311 3005 7274 11121 2433 10408 3147 4419 2536 302 3314 11593 8143 5496 9052 2398 5684 8460 5320 4137 6427 7092 7170 2160 7881 12200 9637 7160 11379 6501 6887 11366 11103 433 11837 8370 1378 10234 9686 4802 9967 8762 1941 11091 1272 4861 3949 9323 2552 10617 6932 9498 4151 9893 3392 5468 1597 5925 3654 11581 4880 3159 11967 6457 12315 73 10193 379 42 6363 10239 7058 7046 11834 6938 2690 624 2103 4895 12039 10008 1781 8703 6929 10201 5117 11203 11472 12278 6264 9883 7990 10090 6055 9195 11592 1794 631 151 2299

[出力例]
56257246

[入力例]
500
2022 201 9128 2421 2021 7838 4217 7697 6106 3519 2530 2020 36850 74953 81006 6586 75551 75587 89606 97002 90356 53482 68575 32184 40607 97434 82571 96320 67400 5288 62749 28206 16596 68956 44467 58071 32198 12177 38396 87606 8878 8328 5442 2604 11263 5746 9314 3185 9707 8443 6781 6069 78336 22629 66983 57454 11210 13429 18214 4748 37107 56141 30904 6090 52272 56768 24634 46301 31230 80753 89021 3010 37346 93387 82126 12093 12608 17978 53423 74226 2023 3430 6408 2901 831 10520 1770 77 4391 4732 8497 816 84121 79525 10364 36137 91959 88459 79189 83697 41671 47523 86573 66963 49365 96912 27040 49627 51013 28984 4422 20422 41663 55405 43797 72935 526 75488 78575 53208 3748 21 47187 15692 99829 73396 53088 59700 44996 26251 62733 7159 10568 47912 76834 11125 36691 92107 77681 12267 41984 18140 19458 69994 48491 71718 4092 52312 3859 77592 154 87621 62891 51680 95331 44261 99627 79691 47902 61496 2042 73729 82578 18211 87616 66537 9270 28247 62047 48493 67427 74212 5911 9323 62395 15860 69836 65638 45323 69937 27612 62302 91630 70699 31562 99945 74847 98208 93698 24938 45429 81630 41668 83458 86860 99346 38529 24653 56694 49841 537 69836 71872 5091 49410 62308 43100 11655 24227 58868 13060 20138 56084 79366 5976 72380 34267 48843 10699 83236 16455 8880 63583 42850 3360 96190 57503 74318 96263 9235 25627 28002 51003 51747 39416 50431 54799 62224 25260 66736 8940 8111 1762 8679 11109 8493 11411 8463 7669 2814 10385 4207 93708 85624 5302 3015 28477 41998 2815 8990 74706 33739 8228 13684 91311 59172 9386 83223 35239 93946 89843 64368 261 81098 12635 81335 26437 22482 66705 93153 4575 9948 9077 2313 2853 6878 3553 11149 576 8258 6030 8205 27029 7237 4787 45750 75836 62048 17419 1239 38698 55820 61621 39252 35735 9526 90954 20445 34462 80247 97356 29152 34026 81642 1129 54421 1268 71422 25902 77406 914 4398 2985 5899 10732 10527 9285 11999 9119 7887 1391 10115 91022 28588 39817 4089 39947 92356 11862 2834 87016 45160 31449 99069 77310 52554 46266 87437 60960 50378 25877 21974 19153 25206 33676 1807 53187 94962 10715 27503 257 80385 33580 39733 64465 38383 73376 93367 85322 82701 12204 48047 91653 82387 947 96429 32658 31214 78454 54972 97562 30560 40927 8651 8551 13003 67128 57126 23699 15748 26560 79089 89411 5856 92127 8143 85591 62414 25865 80307 7590 67728 10839 5003 80955 7764 32687 61960 84805 51602 96761 36656 54364 32088 30884 6163 914 75454 4530 48225 20714 66462 91001 44085 59502 86741 78576 6845 45923 68074 46890 28115 91780 77622 76858 50207 44485 28853 22212 42017 5696 43012 24388 84984 25247 57477 15030 60358 4452 25719 28575 99935 88593 85944 56417 42759 89472 10755 5753 48079 73830 46030 33460 22140 80585 52689 4197 65869 34352 13572 32431 28575 85507 71483 44097 45230 28203 72456 29921 45166 2813 48695 10433 44958 33567 73783 56175 54372 97977 47476 8480 42124 95798 42649 15437 18304 88457 59373 236 77119

[出力例]
980143863

[入力例]

1 2 3

[出力例]

※AtCoderテストケースより

[入力例]

3 1 4 1 5 9 2 6 5 3

[出力例]

237

※AtCoderテストケースより

[入力例]

3 14 159 2653 58979 323846 2643383 27950288 419716939 9375105820

[出力例]

103715602

※AtCoderテストケースより

[入力例]

1 2 3 4 5 6 7

[出力例]

[入力例]

95 88 5 63 67 35 67 2 31 39 0 66

[出力例]

4098

[入力例]

120

7728 7084 5138 10586 3785 8265 10064 9492 9517 6355 1229 8848 11106 9216 10861 6522 3376 7719 6997 10628 7311 3005 7274 11121 2433 10408 3147 4419 2536 302 3314 11593 8143 5496 9052 2398 5684 8460 5320 4137 6427 7092 7170 2160 7881 12200 9637 7160 11379 6501 6887 11366 11103 433 11837 8370 1378 10234 9686 4802 9967 8762 1941 11091 1272 4861 3949 9323 2552 10617 6932 9498 4151 9893 3392 5468 1597 5925 3654 11581 4880 3159 11967 6457 12315 73 10193 379 42 6363 10239 7058 7046 11834 6938 2690 624 2103 4895 12039 10008 1781 8703 6929 10201 5117 11203 11472 12278 6264 9883 7990 10090 6055 9195 11592 1794 631 151 2299

[出力例]

56257246

[入力例]

500

2022 201 9128 2421 2021 7838 4217 7697 6106 3519 2530 2020 36850 74953 81006 6586 75551 75587 89606 97002 90356 53482 68575 32184 40607 97434 82571 96320 67400 5288 62749 28206 16596 68956 44467 58071 32198 12177 38396 87606 8878 8328 5442 2604 11263 5746 9314 3185 9707 8443 6781 6069 78336 22629 66983 57454 11210 13429 18214 4748 37107 56141 30904 6090 52272 56768 24634 46301 31230 80753 89021 3010 37346 93387 82126 12093 12608 17978 53423 74226 2023 3430 6408 2901 831 10520 1770 77 4391 4732 8497 816 84121 79525 10364 36137 91959 88459 79189 83697 41671 47523 86573 66963 49365 96912 27040 49627 51013 28984 4422 20422 41663 55405 43797 72935 526 75488 78575 53208 3748 21 47187 15692 99829 73396 53088 59700 44996 26251 62733 7159 10568 47912 76834 11125 36691 92107 77681 12267 41984 18140 19458 69994 48491 71718 4092 52312 3859 77592 154 87621 62891 51680 95331 44261 99627 79691 47902 61496 2042 73729 82578 18211 87616 66537 9270 28247 62047 48493 67427 74212 5911 9323 62395 15860 69836 65638 45323 69937 27612 62302 91630 70699 31562 99945 74847 98208 93698 24938 45429 81630 41668 83458 86860 99346 38529 24653 56694 49841 537 69836 71872 5091 49410 62308 43100 11655 24227 58868 13060 20138 56084 79366 5976 72380 34267 48843 10699 83236 16455 8880 63583 42850 3360 96190 57503 74318 96263 9235 25627 28002 51003 51747 39416 50431 54799 62224 25260 66736 8940 8111 1762 8679 11109 8493 11411 8463 7669 2814 10385 4207 93708 85624 5302 3015 28477 41998 2815 8990 74706 33739 8228 13684 91311 59172 9386 83223 35239 93946 89843 64368 261 81098 12635 81335 26437 22482 66705 93153 4575 9948 9077 2313 2853 6878 3553 11149 576 8258 6030 8205 27029 7237 4787 45750 75836 62048 17419 1239 38698 55820 61621 39252 35735 9526 90954 20445 34462 80247 97356 29152 34026 81642 1129 54421 1268 71422 25902 77406 914 4398 2985 5899 10732 10527 9285 11999 9119 7887 1391 10115 91022 28588 39817 4089 39947 92356 11862 2834 87016 45160 31449 99069 77310 52554 46266 87437 60960 50378 25877 21974 19153 25206 33676 1807 53187 94962 10715 27503 257 80385 33580 39733 64465 38383 73376 93367 85322 82701 12204 48047 91653 82387 947 96429 32658 31214 78454 54972 97562 30560 40927 8651 8551 13003 67128 57126 23699 15748 26560 79089 89411 5856 92127 8143 85591 62414 25865 80307 7590 67728 10839 5003 80955 7764 32687 61960 84805 51602 96761 36656 54364 32088 30884 6163 914 75454 4530 48225 20714 66462 91001 44085 59502 86741 78576 6845 45923 68074 46890 28115 91780 77622 76858 50207 44485 28853 22212 42017 5696 43012 24388 84984 25247 57477 15030 60358 4452 25719 28575 99935 88593 85944 56417 42759 89472 10755 5753 48079 73830 46030 33460 22140 80585 52689 4197 65869 34352 13572 32431 28575 85507 71483 44097 45230 28203 72456 29921 45166 2813 48695 10433 44958 33567 73783 56175 54372 97977 47476 8480 42124 95798 42649 15437 18304 88457 59373 236 77119

[出力例]

980143863

■参照サイト
AtCoder Beginner Contest 147

C++の練習を兼ねて, AtCoder Beginner Contest 147 の 問題D (Xor Sum 4) を解いてみた.

コメントを残す コメントをキャンセル

C++の練習を兼ねて, AtCoder Beginner Contest 147 の問題D (Xor Sum 4) を解いてみた.

コメントを残すコメントをキャンセル