Submission #70078008

---

Source Code Expand

#include <bits/stdc++.h>
//#define int long long 
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define fr first
#define se second
#define endl '\n'
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;

const int maxn = 2e5 + 5;


void solve()
{
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for(int i = 0; i < n; i ++){
        cin >> a[i];
    }

    if(n == 1){
        cout << (a[0] == 0) + 1 << endl;
        return;
    }

    auto mod = [&](int x){
        if(x >= m) x -= m;
        return x;
    };

    unordered_map<int,int> mp;
    function<void(int, int, vector<int>&)> dfs = [&](int pos, int sum, vector<int>& vec){ // 暴力找合法的子序列
        if(pos >= (int)vec.size()){
            mp[sum] ++;
            return;
        }
        dfs(pos + 2, mod(sum + vec[pos]), vec);
        dfs(pos + 1, sum, vec);
    };

    auto work = [&](int start, vector<int>& vec) -> unordered_map<int,int>{
        dfs(0, start, vec);
        return mp;
    };

    int mid = (n - 1) / 2;
    vector<int> vecl, vecr;
    for(int i = 0; i < n; i ++){
        if(i <= mid) vecl.pb(a[i]);
        else vecr.pb(a[i]);
    }
    auto mpl = work(0, vecl);
    mp.clear();
    auto mpr = work(0, vecr);
    mp.clear();

    ll ans = 0;
    for(auto &[r, cnt] : mpl){
        if(mpr.count(mod(m - r))) ans += 1ll * cnt * mpr[mod(m - r)];
    }

    vecl.clear(); vecr.clear();
    for(int i = 0; i < n; i ++){
        if(i < mid - 1) vecl.pb(a[i]);
        if(i > mid + 2) vecr.pb(a[i]);
    }

    mpl = work(a[mid], vecl);
    mp.clear();
    mpr = work(a[mid + 1], vecr);
    mp.clear();

    for(auto &[r, cnt] : mpl){
        if(mpr.count(mod(m - r))) ans -= 1ll * cnt * mpr[mod(m - r)];
    }

    cout << ans << endl;
}


signed main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    // int T=1; cin>>T; while(T--)
    solve();
    return 0;
}

Submission Info

Judge Result