問題概述

原題參考A.新春游戲之數學系列
大致就是給出一個數組，要求求出一個公式的值，有幾個數據范圍值得注意一下，一是數組的長度為[0, 1e6]，二是數組元素的和不超過5e7

思路分析

賽時第一眼準備去分析公式看看有沒有可以優化的，用前綴拆分優化一下，但是沒找到，因此就暫時擱置，畢竟這個n的大小肯定是不能O(n²)的，之后的優化又走錯方向了，想著把求二進制數的1的個數優化一下，用map記錄，但是沒有用，這樣還是跑不掉n²的時間；
事實上，該題的重點在于上面標記的位置數組元素的和不超過5e7，根據這個我們可以求出數組中不同元素的個數事實上是小于1e4的，這樣的話我們就可以通過map記錄，遍歷map得到答案
至于1e4是怎么得到的，1+2+...+k <= 5e7，k<1e4的這樣就可以通過一個O(k²)解決該問題

參考代碼

#include <bits/stdc++.h>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define pll pair<long long, long long>
#define pii pair<int, int>
#define vi vector<int>
#define vl vector<long long>
#define ll long long
#define ull unsigned long long
const ll INF = 9187201950435737471;
const int inf = 2139062143;
const ll mod = 998244353;
const double eps = 1e-6;
const double PI = acos(-1.0);
const int N = 1e6+7;
map<int, int> _cnt;
int n, a[N];
ll ans = 0;
int gcd(int a, int b) {
    return b ? gcd(b, a%b) : a;
}
int lowbit(int x) {return x&-x;}
int cnt(int x) {
    int res = 0;
    while(x) {
        res ++;
        x -= lowbit(x);
    }
    return res;
}
void solve() {
    cin >> n;
    for(int i=1; i<=n; i++) {
        cin >> a[i];
        _cnt[a[i]] ++;
    }
    for(auto x:_cnt) {
        for(auto y:_cnt) {
            ans += (_cnt[x.first] * _cnt[y.first] % mod) * gcd(x.first, y.first) %mod * (cnt(x.first) + cnt(y.first));
            ans %= mod;
        }
    }
    cout << ans << endl;
}
int main() {
#ifdef xrl
    freopen("in.txt", "r", stdin), freopen("out.txt", "w", stdout);
#endif
    FAST_IO;
    int t = 1;
    //cin >> t;
    while(t --) solve();
#ifdef xrl
    cout << "Time used = " << (double)(clock() * 1.0 / CLOCKS_PER_SEC) << "s";
#endif
    return 0;
}

做題反思

這個題沒做出來其實還是做得少了，沒有經驗，就像是之前的拆分也是，事實上，我甚至沒有注意到那個元素和小于5e7的條件，別說利用這個條件去縮小數據范圍了