Submission #34751028

---

Source Code Expand

    #include <bits/stdc++.h>

    #include <ext/pb_ds/assoc_container.hpp>
    #include <ext/pb_ds/tree_policy.hpp>
    // #pragma GCC target("popcnt")

using namespace std;
using namespace __gnu_pbds;

    template <typename t>
using ordered_set = tree<t, null_type, less<t>, rb_tree_tag, tree_order_statistics_node_update>;

    // #pragma gcc optimize("ofast")
    // #pragma gcc target("avx,avx2,fma")


    #define int long long

    #define all(x) (x).begin(), (x).end()


    #define pb push_back
    #define endl '\n'
    #define fi first
    #define se second

    // const int mod = 1e9 + 7;

const int mod=998'244'353;


const long long INF = 2e18 + 10;
    // const int INF=1e9+10;

    #define readv(x, n)   \
vector<int> x(n); \
for (auto &i : x) \
    cin >> i;



    template <typename t>
using v = vector<t>;

    template <typename t>
using vv = vector<vector<t>>;

    template <typename t>
using vvv = vector<vector<vector<t>>>;

typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<vector<int>> vvi;
typedef vector<vector<vector<int>>> vvvi;
typedef vector<vector<vector<vector<int>>>> vvvvi;
typedef vector<vector<double>> vvd;

typedef pair<int, int> pii;



int multiply(int a, int b, int in_mod) { return (int)(1ll * a * b % in_mod); }
int mult_identity(int a) { return 1; }



const double pi = acosl(-1);



auto power(auto a, auto b, const int in_mod)
{

    auto prod = mult_identity(a);
    auto mult = a % in_mod;
    while (b != 0)
    {
        if (b % 2)
        {
            prod = multiply(prod, mult, in_mod);
        }
        if(b/2)
            mult = multiply(mult, mult, in_mod);
        b /= 2;
    }
    return prod;
}
auto mod_inv(auto q, const int in_mod)
{
    return power(q, in_mod - 2, in_mod);
}


mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());



#define stp cout << fixed << setprecision(20);
#define trie asdfads

const int K = 26;

struct Vertex {
    int next[K];
    bool leaf = false;
    int dc = 0;

    Vertex() {
        fill(begin(next), end(next), -1);
    }
};

vector<Vertex> trie(1);


pair<int,int> add_string(string const& s) {
    int v = 0;

    int cnt = 0;

    for (char ch : s) {
        int c = ch - 'a';
        if (trie[v].next[c] == -1) {
            trie[v].next[c] = trie.size();
            trie.emplace_back();
        }
        if(trie[v].leaf)
            cnt++;
        v = trie[v].next[c];
    }
    trie[v].leaf = true;
    return {cnt,trie[v].dc  - 1};
}

void calc_trie()
{
    for(int i = trie.size() - 1;i>=0;i--)
    {
        if(trie[i].leaf)
            trie[i].dc ++;

        for(int j= 0;j<K;j++)
        {
            if(trie[i].next[j] != -1)
            {
                trie[i].dc += trie[trie[i].next[j]].dc;
            }
        }
    }

} 

void solv()
{
    int n;
    cin>>n;

    vector<string> s(n);

    for(int i = 0;i<n;i++)
    {
        cin>>s[i];
        add_string(s[i]);
    }
    calc_trie();

    for(int i = 0;i<n;i++)
    {
        pair<int,int> cnt = add_string(s[i]);

        int strict_less = cnt.fi  + 1;
        int strict_greater = cnt.se;


        int free = ( n - strict_less - strict_greater ) * mod_inv(2,mod) %mod;
        cout<<(free + strict_less)%mod<<endl;

    }




}

void solve()
{

    int t = 1;
        // cin>>t;
    while(t--)
    {
        solv();
    }
}




signed main()
{



    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cerr.tie(NULL);

    auto clk = clock();
        // -------------------------------------Code starts here---------------------------------------------------------------------

    signed t = 1;
        // cin >> t;

    for (signed test = 1; test <= t; test++)
    {
            // cout<<"Case #"<<test<<": ";

        solve();
    }

        // -------------------------------------Code ends here------------------------------------------------------------------

    clk = clock() - clk;

        #ifndef ONLINE_JUDGE
    cerr << fixed << setprecision(6) << "\nTime: " << ((float)clk) / CLOCKS_PER_SEC << "\n";
        #endif
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘long long int mult_identity(long long int)’:
./Main.cpp:63:23: warning: unused parameter ‘a’ [-Wunused-parameter]
   63 | int mult_identity(int a) { return 1; }
      |                       ^
./Main.cpp: At global scope:
./Main.cpp:71:12: warning: use of ‘auto’ in parameter declaration only available with ‘-fconcepts’
   71 | auto power(auto a, auto b, const int in_mod)
      |            ^~~~
./Main.cpp:71:20: warning: use of ‘auto’ in parameter declaration only available with ‘-fconcepts’
   71 | auto power(auto a, auto b, const int in_mod)
      |                    ^~~~
./Main.cpp:88:14: warning: use of ‘auto’ in parameter declaration only available with ‘-fconcepts’
   88 | auto mod_inv(auto q, const int in_mod)
      |              ^~~~

Judge Result