Language: C++

#include<bits/stdc++.h>
using namespace std;
// #include <ext/pb_ds/assoc_container.hpp> 
// #include <ext/pb_ds/detail/standard_policies.hpp>
// using namespace __gnu_pbds;

#pragma GCC optimize("O3")
#ifdef LOCAL
#include "/Users/lbjlc/Desktop/coding/debug_utils.h"
#else
#define print(...) ;
#define printn(...) ;
#define printg(...) ;
#define fprint(...) ;
#define fprintn(...) ;
#endif

#define rep(i, a, b) for(auto i = (a); i < (b); i++)
#define rrep(i, a, b) for(auto i = (a); i > (b); i--)
#define all(v) (v).begin(), (v).end()
#define pb push_back
// #define mp make_pair
#define fi first
#define se second
#define maxi(x, y) x = max(x, y)
#define mini(x, y) x = min(x, y)
// long long fact(long long n) { if(!n) return 1; return n*fact(n-1); }
// #define endl '\n'
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define solve_testcase int T;cin>>T;for(int t=1;t<=T;t++){solve(t);}


typedef unsigned long long ull;
typedef long long ll;
 
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
 
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<pdd> vpdd;
typedef vector<long long> vll;
#define bd(type,op,val) bind(op<type>(), std::placeholders::_1, val)

template<class T>
void make_unique(T & v) {
    sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());
}
int geti() { int x; cin >> x; return x; }
long long getll() { long long x; cin >> x; return x; }
double getd() { double x; cin >> x; return x; }
// pair<int, int> a(geti(), geti()) does not work
// pair<int, int> a({geti(), geti()}) works, since it uses initializer.

const int MAXN = 1e6+500;


void solve(int tt) {
    cout<<"Case #"<<tt<<": ";
}

vector<vector<bool>> dp(1<<20,vi(26));
struct Trie{
    int nxt[MAXN][26] = {};
    short cnt[MAXN] = {};
    short cntp[MAXN] = {};
    short cntpc[MAXN][26] = {};
    int head = 1, tot = 1; // head is idx of head node, tot is the last allocated node

    int & __alloc() {
        cnt[++tot] = 0;
        memset(nxt[tot], 0, sizeof(nxt[tot]));
        return tot;
    }

    void clear() { tot = 0; head = __alloc(); }

    void insert(const string & s) {
        int n = s.size();
        dp[n] = vector<bool>(26);
        rrep(i,n-1,-1){
            dp[i]=dp[i+1];
            dp[i][s[i]-'a']=1;
        }
        print(s);
        // print(dp[0]);
        // print(dp[1]);
        // print(dp[2]);
        // print(dp[3]);

        int tmp = head;

        cntp[tmp]++;
        rep(j,0,26) if(dp[0][j]) cntpc[tmp][j]++;
        // printn(cntpc[tmp],26);

        for(int i = 0; i < s.size(); i++) {
            if(nxt[tmp][s[i] - 'a']) tmp = nxt[tmp][s[i] - 'a'];
            else tmp = nxt[tmp][s[i] - 'a'] = __alloc();

            cntp[tmp]++;
            rep(j,0,26) if(dp[i+1][j]) cntpc[tmp][j]++;
        }
        // print("visiting node ", tmp);
        cnt[tmp]++;
    }

    int count(const string & s) {
        int n=s.size();
        int res=0;

        int tmp = head;
        if(n==1) res+=cntpc[tmp][s.back() - 'a'];
        for(int i = 0; i < s.size(); i++) {
            if(!nxt[tmp][s[i] - 'a']) break;
            tmp = nxt[tmp][s[i] - 'a'];

            if(i==n-2) res+=cntpc[tmp][s.back() - 'a'];
            // else if(i==n-1) res+=cntp[tmp];

        }
        res+=cnt[tmp];
        return res;
    }
} trie;

int n;
string s[MAXN];

int main(int argc, char * argv[]) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    // solve_testcase;

    cin>>n;
    rep(i,0,n) {
        cin>>s[i];
        reverse(all(s[i]));
    }
    sort(s,s+n,[](const string & x, const string & y) {
        if(x.size()!=y.size()) return x.size() > y.size();
        else return x < y;
    });

    printn(s,n);

    ll res=0;
    rep(i,0,n) {
        res+=trie.count(s[i]);
        trie.insert(s[i]);
        print(res);
    }
    cout<<res<<endl;


    return 0;
}




















Compiler output:
a.cc:66:37: error: no matching function for call to 'std::vector<std::vector<bool> >::vector(int, vi)'
   66 | vector<vector<bool>> dp(1<<20,vi(26));
      |                                     ^
In file included from /usr/include/c++/14/vector:66,
                 from /usr/include/c++/14/functional:64,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:53,
                 from a.cc:1:
/usr/include/c++/14/bits/stl_vector.h:707:9: note: candidate: 'template<class _InputIterator, class> std::vector<_Tp, _Alloc>::vector(_InputIterator, _InputIterator, const allocator_type&) [with <template-parameter-2-2> = _InputIterator; _Tp = std::vector<bool>; _Alloc = std::allocator<std::vector<bool> >]'
  707 |         vector(_InputIterator __first, _InputIterator __last,
      |         ^~~~~~
/usr/include/c++/14/bits/stl_vector.h:707:9: note:   template argument deduction/substitution failed:
a.cc:66:37: note:   deduced conflicting types for parameter '_InputIterator' ('int' and 'std::vector<int>')
   66 | vector<vector<bool>> dp(1<<20,vi(26));
      |                                     ^
/usr/include/c++/14/bits/stl_vector.h:678:7: note: candidate: 'std::vector<_Tp, _Alloc>::vector(std::initializer_list<_Tp>, const allocator_type&) [with _Tp = std::vector<bool>; _Alloc = std::allocator<std::vector<bool> >; allocator_type = std::allocator<std::vector<bool> >]'
  678 |       vector(initializer_list<value_type> __l,
      |       ^~~~~~
/usr/include/c++/14/bits/stl_vector.h:678:43: note:   no known conversion for argument 1 from 'int' to 'std::initializer_list<std::vector<bool> >'
  678 |       vector(initializer_list<value_type> __l,
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/14/bits/stl_vector.h:659:7: note: candidate: 'std::vector<_Tp, _Alloc>::vector(std::vector<_Tp, _Alloc>&&, std::__type_identity_t<_Alloc>&) [with _Tp = std::vector<bool>; _Alloc = std::allocator<std::vector<bool> >; std::__type_identity_t<_Alloc> = std::allocator<std::vector<bool> >]'
  659 |       vector(vector&& __rv, const __type_identity_t<allocator_type>& __m)
      |       ^~~~~~
/usr/include/c++/14/bits/stl_vector.h:659:23: note:   no known conversion for argument 1 from 'int' to 'std::vector<std::vector<bool> >&&'
  659 |       vector(vector&& __rv, const __type_identity_t<allocator_type>& __m)
      |              ~~~~~~~~~^~~~
/usr/include/c++/14/bits/stl_vector.h:640:7: note: candidate: 'std::vector<_Tp, _Alloc>::vector(std::vector<_Tp, _Alloc>&&, const allocator_type&, std::false_type) [with _Tp = std::vector<bool>; _Alloc = std::allocator<std::vector<bool> >; allocator_type = std::allocator<std::vector<bool> >; std::false_type = std::false_type]'
  640 |       vector(vector&& __rv, const allocator_type& __m, false_type)
      |       ^~~~~~
/usr/include/c++/14/bits/stl_vector.h:640:7: note:   candidate expects 3 arguments, 2 provided
/usr/include/c++/14/bits/stl_vector.h:635:7: note: candidate: 'std::vector<_Tp, _Alloc>::vector(std::vector<_Tp, _Alloc>&&, const allocator_type&, std::true_type) [with _Tp = std::vector<bool>; _Alloc = std::allocator<std::vector<bool> >; allocator_type = std::allocator<std::vector<bool> >; std::true_type = std::true_type]'
  635 |       vector(vector&& __rv, const allocator_type& __m, true_type) noexcept
      |       ^~~~~~
/usr/include/c++/14/bits/stl_vector.h:635:7: note:   candidate expects 3 arguments, 2 provided
/usr/include/c++/14/bits/stl_vector.h:624:7: note: candidate: 'std::vector<_Tp, _Alloc>::vector(const std::vector<_Tp, _Alloc>&, std::__type_identity_t<_Alloc>&) [with _Tp = std::vector<bool>; _Alloc = std::allocator<std::vector<bool> >; std::__type_identity_t<_Alloc> = std::allocator<std::vector<bool> >]'
  624 |       vector(const vector& __x, const __type_identity_t<allocator_type>& __a)
      |       ^~~~~~
/usr/include/c++/14/bits/stl_vector.h:624:28: note:   no known conversion for argument 1 from 'int' to 'const std::vector<std::vector<bool> >&'
  624 |       vector(const vector& __x, const __type_identity_t<allocator_type>& __a)
      |              ~~~~~~~~~~~~~~^~~
/usr/include/c++/14/bits/stl_vector.h:620:7: note: candidate: 'std::vector<_Tp, _Alloc>::vector(std::vector<_Tp, _Alloc>&&) [with _Tp = std::vector<bool>; _Alloc = std::allocator<std::vector<bool> >]'
  620 |       vector(vector&&) noexcept = default;
      |       ^~~~~~
/usr/include/c++/14/bits/stl_vector.h:620:7: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/14/bits/stl_vector.h:601:7: note: candidate: 'std::vector<_Tp, _Alloc>::vector(const std::vector<_Tp, _Alloc>&) [with _Tp = std::vector<bool>; _Alloc = std::allocator<std::vector<bool> >]'
  601 |       vector(const vector& __x)
      |       ^~~~~~
/usr/include/c++/14/bits/stl_vector.h:601:7: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/14/bits/stl_vector.h:569:7: note: candidate: 'std::vector<_Tp, _Alloc>::vector(size_type, const value_type&, const allocator_type&) [with _Tp = std::vector<bool>; _Alloc = std::allocator<std::vector<bool> >; size_type = long unsigned int; value_type = std::vector<bool>; allocator_type = std::allocator<std::vector<bool> >]'
  569 |       vector(size_type __n, const value_type& __value,
      |       ^~~~~~
/usr/include/c++/14/bits/stl_vector.h:569:47: note:   no known conversion for argument 2 from 'vi' {aka 'std::vector<int>'} to 'const std::vector<std::vector<bool> >::value_type&' {aka 'const std::vector<bool>&'}
  569 |       vector(size_type __n, const value_type& __value,
      |                             ~~~~~~~~~~~~~~~~~~^~~~~~~
/usr/include/c++/14/bits/stl_vector.h:556:7: note: candidate: 'std::vector<_Tp, _Alloc>::vector(size_type, const allocator_type&) [with _Tp = std::vector<bool>; _Alloc = std::allocator<std::vector<bool> >; size_type = long unsigned int; allocator_type = std::allocator<std::vector<bool> >]'
  556 |       vector(size_type __n, const allocator_type& __a = allocator_type())
      |       ^~~~~~
/usr/include/c++/14/bits/stl_vector.h:556:51: note:   no known conversion for argument 2 from 'vi' {aka 'std::vector<int>'} to 'const std::vector<std::vector<bool> >::allocator_type&' {aka 'const std::allocator<std::vector<bool> >&'}
  556 |       vector(size_type __n, const allocator_type& __a = allocator_type())
      |                             ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_vector.h:542:7: note: candidate: 'std::vector<_Tp, _Alloc>::vector(const allocator_type&) [with _Tp = std::vector<bool>; _Alloc = std::allocator<std::vector<bool> >; allocator_type = std::allocator<std::vector<bool> >]'
  542 |       vector(const allocator_type& __a) _GLIBCXX_NOEXCEPT
      |       ^~~~~~
/usr/include/c++/14/bits/stl_vector.h:542:7: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/14/bits/stl_vector.h:531:7: note: candidate: 'std::vector<_Tp, _Alloc>::vector() [with _Tp = std::vector<bool>; _Alloc = std::allocator<std::vector<bool> >]'
  531 |       vector() = default;
      |       ^~~~~~
/usr/include/c++/14/bits/stl_vector.h:531:7: note:   candidate expects 0 arguments, 2 provided