Untitled

 avatar
unknown
plain_text
9 months ago
1.9 kB
10
Indexable
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
template<class T> using orderedset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
int dx[] = {0, 0, 1, -1, 1, 1, -1, -1};
int dy[] = {1, -1, 0, 0, 1, -1, 1, -1};
void File() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("errors.txt", "w", stderr);
#else

#endif
}
int main() {
    File();
    int tt;
    cin >> tt;
    for (int tc = 1; tc <= tt; tc++) {
        string s;
        cin >> s;
        vector<int> digit;
        for (auto &c: s)
            digit.push_back(c - '0');
        sort(digit.begin(), digit.end());
        digit.erase(unique(digit.begin(), digit.end()), digit.end());
        ll sz = digit.size(), ans = 0;
        for (int mask = 0; mask < (1 << sz) - 1; ++mask) {
            vector<bool> ignore(10, true);
            for (int i = 0; i < sz; ++i)
                if (!(mask & (1 << i)))
                    ignore[digit[i]] = false;
            map<vector<int>, int> frq;
            vector<int> cur(10, 0);
            frq[cur]++;
            for (int i = 0; i < s.size(); ++i) {
                if (ignore[s[i] - '0']) {
                    frq.clear();
                    cur.assign(10, 0);
                    frq[cur]++;
                    continue;
                }
                cur[s[i] - '0'] ^= 1;
                vector<int> comp(10, 0);
                for (int j = 0; j < 10; ++j)
                    comp[j] = cur[j] ^ 1 ^ ignore[j];
                ans += frq[comp];
                frq[cur]++;
            }
        }
        cout << ans << endl;
    }
    return 0;
}
Editor is loading...
Leave a Comment