Записи в блоге

Problem A

Problem B

This is a constructive problem.

Let’s analyze all possible combinations of consecutive bits and how their OR and AND behave.

Ans[i]	Ans[i+1]	OR (A[i])	AND (B[i])
0	0	0	0
0	1	1	0
1	0	1	0
1	1	1	1

Key Observations

Invalid Combination:
For (OR, AND) = (0, 1) there is no valid configuration.
Hence, if this case appears in the input, the answer is immediately -1.
Fixed Configurations:

(OR, AND) = (0, 0) → Only possible as (0, 0)
(OR, AND) = (1, 1) → Only possible as (1, 1)
So these positions are fixed during construction.

Flexible Configurations:
For (OR, AND) = (1, 0), there are two valid possibilities:

(0, 1) or (1, 0)
These will be the free bits to be filled later between fixed ones.

Continuity Constraint:
You cannot have consecutive fixed pairs like:

(00) followed by (11) directly, or
(11) followed by (00)
because they contradict continuity in construction.

Parity Observation:
Between any two fixed configurations:

(00 → 00) or (11 → 11) ⇒ only even number of (OR, AND) = (1,0) configurations allowed
(00 → 11) or (11 → 00) ⇒ only odd number of (OR, AND) = (1,0) configurations allowed

If this parity condition is not met, the answer is -1.

Construction Approach

Check invalid pairs:
If any (OR, AND) = (0, 1) → print -1.
Fix known bits:
Mark all positions where (OR, AND) is (0,0) or (1,1).
Check for conflicts:
If any contradiction appears between fixed bits → print -1.
Fill middle parts:

Between two fixed blocks, fill alternately using the parity rule.
If no fixed blocks exist at all, fill arbitrarily as:
- 010101... or
- 101010...

Verification:
After construction, verify that the generated array indeed satisfies all (OR, AND) pairs.
If yes, add the corresponding bit to the final answer.

Mutliple answer can be possible.

Code

Problem C

Euler Tour (Tree Flattening)

We perform a DFS and record for each node u:

in[u]: the time we enter u

out[u]: the time we exit u

During the traversal, we build a array by adding each node’s value when entered and again when exited. All nodes in u’s subtree appear in the range [in[u], out[u]], and since each value appears twice, this range’s sum equals twice the subtree sum.

Segment Tree with Lazy Propagation

We build a Segment Tree over array to handle range operations efficiently:

Type 1 (Sum Query): Query the Segment Tree for [in[a], out[a]] and divide the result by 2.

Type 2 (Flip Query): Flip all values in [in[a], out[a]].

Lazy propagation allows us to handle range updates efficiently. Instead of immediately updating every element in a range, we mark that range with a lazy flag indicating it needs to be flipped later. When the range is accessed, the flip is applied, and the flag is passed down to its children.

Each flip acts as a toggle — flipping twice restores the original values. This approach ensures that both updates and queries on the Segment Tree take only O(log N) time.

Code

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define f(i, a, b) for (int i = a; i < b; i++)
#define fastio                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);

void build(int ind, int lo, int hi, vector<int> &seg, vector<int> &a)
{
    if (lo == hi)
    {
        seg[ind] = a[lo];
        return;
    }
    int mid = lo + (hi - lo) / 2;
    build(2 * ind + 1, lo, mid, seg, a);
    build(2 * ind + 2, mid + 1, hi, seg, a);
    seg[ind] = seg[2 * ind + 1] + seg[2 * ind + 2];
}

void sumrangeupdate(vector<int> &seg, vector<int> &lazy, int ind, int lo, int hi, int l, int r)
{
    if (lazy[ind] != 0)
    {
        seg[ind] = (-seg[ind]);
        if (lo != hi)
        {
            lazy[2 * ind + 1] = 1 - lazy[2 * ind + 1];
            lazy[2 * ind + 2] = 1 - lazy[2 * ind + 2];
        }
        lazy[ind] = 0;
    }
    if (lo > r || hi < l || lo > hi)
        return;
    if (l <= lo && hi <= r)
    {
        seg[ind] = (-seg[ind]);
        if (lo != hi)
        {
            lazy[2 * ind + 1] = 1 - lazy[2 * ind + 1];
            lazy[2 * ind + 2] = 1 - lazy[2 * ind + 2];
        }
        return;
    }
    int mid = lo + (hi - lo) / 2;
    sumrangeupdate(seg, lazy, 2 * ind + 1, lo, mid, l, r);
    sumrangeupdate(seg, lazy, 2 * ind + 2, mid + 1, hi, l, r);
    seg[ind] = seg[2 * ind + 1] + seg[2 * ind + 2];
}

int querysumlazy(vector<int> &seg, vector<int> &lazy, int ind, int lo, int hi, int l, int r)
{
    if (lazy[ind] != 0)
    {
        seg[ind] = (-seg[ind]);
        if (lo != hi)
        {
            lazy[2 * ind + 1] = 1 - lazy[2 * ind + 1];
            lazy[2 * ind + 2] = 1 - lazy[2 * ind + 2];
        }
        lazy[ind] = 0;
    }
    if (lo > r || hi < l || lo > hi)
        return 0;
    if (l <= lo && hi <= r)
    {
        return seg[ind];
    }
    int mid = lo + (hi - lo) / 2;
    return querysumlazy(seg, lazy, 2 * ind + 1, lo, mid, l, r) + querysumlazy(seg, lazy, 2 * ind + 2, 1 + mid, hi, l, r);
}

void dfs(int node, int par, vector<int> g[], vector<int> &v, vector<int> &a, vector<int> &in, vector<int> &out, int &t)
{
    in[node] = t++;
    v.pb(a[node]);
    for (auto &child : g[node])
    {
        if (par == child)
            continue;
        dfs(child, node, g, v, a, in, out, t);
    }
    out[node] = t++;
    v.pb(a[node]);
}
void solve()
{
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    vector<int> g[n];
    f(i, 0, n - 1)
    {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        g[u].pb(v);
        g[v].pb(u);
    }
    vector<int> v;
    vector<int> in(n);
    vector<int> out(n);
    int t = 0;
    dfs(0, -1, g, v, a, in, out, t);
    vector<int> seg(8 * n);
    vector<int> lazy(8 * n, 0);
    build(0, 0, 2 * n - 1, seg, v);
    while (q--)
    {
        int type, a;
        cin >> type >> a;
        a--;
        if (type == 1)
        {
            cout << querysumlazy(seg, lazy, 0, 0, 2 * n - 1, in[a], out[a]) / 2 << endl;
        }
        else
        {
            sumrangeupdate(seg, lazy, 0, 0, 2 * n - 1, in[a], out[a]);
        }
    }
}
signed main()
{
    fastio

        int T;
    cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

Problem D

The core idea is that a number x can be formed if and only if the bitwise AND of all numbers in the input array that are bitwise supersets of x is exactly equal to x.

A number y is a superset of x if (x & y) == x. A naive check for each query would be too slow ($$$O(N \times Q)$$$). We can optimize by precomputing the answers using Dynamic Programming.

We define dp[mask] as the bitwise AND of all input numbers that are supersets of mask.

Initialization: For each number a in our input array, we set dp[a] = a.

DP Transition: We iterate downwards from the maximum possible value. For each mask, we update it by taking the AND with its immediate supersets (masks with one additional bit set): dp[mask] &= dp[mask | (1 << i)].

Why this works: By iterating downwards, we ensure that when we process dp[mask], the value for any of its supersets (like dp[mask | (1 << i)]) has already been finalized. This transition correctly incorporates the AND result from those supersets, because any number that is a superset of mask | (1 << i) is also a superset of mask.

Answering Queries: After precomputation, we can answer any query for x in $$$O(1)$$$ time by simply checking if dp[x] == x. If they are equal, the answer is YES.

The precomputation complexity is $$$O(\text{MAX_VAL} \times \text{BITS})$$$ .

Code

#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;

#define int long long
#define endl '\n'

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
// *find_by_order, order_of_key

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

    int mx = (1<<20) ;
    vector<int> dp(mx , -1) ;

    for(int i=0 ; i<n ; i++){
        dp[arr[i]] = arr[i] ;
    }

    for(int i=mx-1 ; i>=0 ; i--){
        for(int bit = 0 ; bit<20 ; bit++){
            if(i & (1<<bit)){
                dp[i ^ (1<<bit)] &= dp[i] ;
            }
        }
    }

    while(q--){
        int x ;
        cin >> x ;
        if(dp[x] == x){
            cout<<"Yes"<<endl;
        }else{
            cout<<"No"<<endl;
        }
    }
    
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t = 1 ;
    cin >> t ;
    
    while(t--){
        solve();
    }
}

Problem E

Code

#include <algorithm>
#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;
// #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// order_of_key(k) : no. of elements < k
// *find_by_order(i) : value at index i (0-based)
 
#define int long long
#define vi vector<ll>
#define vvi vector<vi>
#define pll pair<ll, ll>
#define vp vector<pll>
#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define M 1000000007
// #define M 998244353
#define INF 1e18
#define endl "\n"
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define ff first
#define ss second
#define fr(i,s,e) for(ll i = s; i < e; i++)
#define forrr(i,s,e) for(ll i = s; i >= e; i--)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define yn(f) f?cout<<"YES\n":cout<<"NO\n"
#define syn(f) f?cout<<"Yes\n":cout<<"No\n"
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;
#ifdef ONLINE_JUDGE
#define debug(x) 
#else
#define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
#endif
 
void _print(ll t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(lld t) {cerr << t;}
void _print(double t) {cerr << t;}
void _print(ull t) {cerr << t;}
 
template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
 
int binpow(int x,int n) {x%=M;if(n==0) return 1; else if(n==1) return x; int p = binpow(x*x, n/2);if(n%2) return p*x%M; else return p;}
int random(int s, int e){return s + rand() % (e - s + 1);}
ll gcd(ll a, ll b){if(b == 0) return a; return gcd(b, a%b);}
ll lcm(ll a, ll b){return a*b/gcd(a,b);}
vi factors(ll n){ vi fac; for (ll i = 1; i * i <= n; i++){ if (n % i == 0){ fac.pb(i); if (i * i != n)fac.pb(n / i); } } return fac; }
int mod_div(int p, int q) { return p%M * binpow(q,M-2) % M;}
vi fact, ifact;
void factCompute(int N=1e6) {fact.assign(N+1, 1);ifact.assign(N+1, 1);fr(i,1,N+1) fact[i] = fact[i-1] * i % M;ifact[N] = mod_div(1, fact[N]); forrr(i,N-1,0) ifact[i] = ifact[i+1] * (i+1) % M; }
int ncr(int n, int r) {if(r > n) return 0; return fact[n] * ifact[n-r] % M * ifact[r] % M;}
vi spf, primes;
void sieve(int N=1e7){spf.assign(N+1,0); fr(i,0,N+1) spf[i]=i;for(int i=2; i*i<=N; i++) if(spf[i]==i) for(int j=i*i; j<=N; j+=i) spf[j]=min(spf[j],i);fr(i,2,N+1) if(spf[i]==i) primes.pb(i);}
 
vvi graph;
vi vec, par;
void dfs(int node, int parent, vector<map<int, multiset<int>>> &p){
    int curr = vec[node];
    par[node] = parent;
    map<int, int> pf;
    while(curr != 1){
        int prime = spf[curr];
        pf[prime]++;
        curr /= prime;
    }
    vp temp;
    for(auto it: pf){
        temp.pb(mp(it.ff, it.ss));
    }
 
    for(auto it: temp){
        p[node][it.ff].insert(it.ss);
        if(parent != -1)
        p[parent][it.ff].insert(it.ss);
    }
 
    for(auto &nbr: graph[node]){
        if(nbr != parent)
        dfs(nbr, node, p);
    }
}
void solve(int tc){
    int n;cin>>n;
    vec.assign(n+1, 0);
    par.assign(n+1, 0);
    fr(i,0,n) cin>>vec[i+1];
 
    graph.assign(n+1, {});
    for(int i=1;i<n;i++){
        int u, v;cin>>u>>v;
        graph[u].pb(v);
        graph[v].pb(u);
    }
    vector<map<int, multiset<int>>> p(n+1); 
    vi gcd1(n+1);
    dfs(1, -1, p);
    int ans = 0;
    for(int i=1;i<=n;i++){
        int currsz = graph[i].size();
        if(i == 1) currsz++;
        int g = 1;
        for(auto it: p[i]){
            if(it.ss.size() == currsz){
                g *= pow(it.ff, *it.ss.begin());
            }
        }
        gcd1[i] = g;
        ans += g;
    }
    // debug(gcd1);
 
    int q;cin>>q;
    while(q--){
        int t;cin>>t;
        if(t == 1){
            int node, val;cin>>node>>val;
            int curr = vec[node], parent = par[node];
            map<int, int> pf;
            ans -= gcd1[node];
            if(parent != -1)
            ans -= gcd1[parent];
 
            curr = vec[node];
            while(curr != 1){
                int prime = spf[curr];
                pf[prime]++;
                curr /= prime;
            }
            vp temp;
            for(auto it: pf){
                temp.pb(mp(it.ff, it.ss));
            }
            for(auto it: temp){
                p[node][it.ff].erase(p[node][it.ff].find(it.ss));
                if(parent != -1)
                p[parent][it.ff].erase(p[parent][it.ff].find(it.ss));
            }
 
 
            vec[node] = val;
            pf.clear();
            curr = vec[node];
            while(curr != 1){
                int prime = spf[curr];
                pf[prime]++;
                curr /= prime;
            }
            temp.clear();
            for(auto it: pf){
                temp.pb(mp(it.ff, it.ss));
            }
 
            int currszn = graph[node].size();int currszp = 0;
            if(parent!= -1) currszp = graph[parent].size();
            if(node == 1) currszn++;
            if(parent == 1) currszp++;
            int gc = 1, gp = 1;
            for(auto it: temp){
                p[node][it.ff].insert(it.ss);
                if(parent != -1)
                p[parent][it.ff].insert(it.ss);
                // debug(p[node][it.ff]);
                // debug(p[parent][it.ff]);
                if(currszn == p[node][it.ff].size()) {
                    gc *= pow(it.ff, *p[node][it.ff].begin());
                }
                if(parent != -1){
                    if(currszp == p[parent][it.ff].size()) {
                        gp *= pow(it.ff, *p[parent][it.ff].begin());
                    }
                }
            }
            
            gcd1[node] = gc;
            if(parent != -1)
            gcd1[parent] = gp;
            if(parent != -1)
            ans += gc + gp;
            else
            ans += gc;
            // debug(gcd1);
        }else{
            cout<<ans<<endl;
        }
    }
}
 
signed main() {
    fastio();
    // factCompute(1e6);
    sieve(1e6);
    ll t = 1;
    // cin>>t;
    fr(i,0,t) solve(i);
    return 0;
}

Problem F1 & F2

Problem G

Hint 1

Hint 2

Solution

Author's Code (C++)

#include<bits/stdc++.h>
using namespace std;
 #define int long
 const int MOD = 6991;
 long long exp(long long x, long long n, long long m) {
     x %= m;
     long long res = 1;
     while (n > 0) {
         if (n % 2 == 1) { res = res * x % m; }
         x = x * x % m;
         n /= 2;}
     return res;}
  long long fun(string &a, int m, int base){
    int res=0;
    for(int i=0;i<a.size();i++){
      res = (res*base + int(a[i]-'0'))%m;}
      return res%m;}
 signed main() {
     ios_base::sync_with_stdio(false); 
     cin.tie(NULL);
     cout.tie(NULL);
     int t;
     cin>>t;
     while(t--){
     int a1,b1,k;
     cin>>a1>>b1>>k;
     string a,b;
     cin>>a>>b;
     int k_inv = exp(k, MOD-2, MOD);
     int term1 = (((fun(a,MOD,2) - fun(a,k,2) + MOD)%MOD) * (k_inv%MOD))%MOD;
     int term2 = (((fun(b,MOD,10) - fun(b,k,10) + MOD)%MOD) * (k_inv%MOD))%MOD;
     int res = (term2 - term1 + MOD)%MOD;
     cout<<res<<endl;}
     return 0;}

Problem H

Hint 1

Hint 2

Solution

Author's Code (C++)

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
 
vector<pair<int, char>> tree[MAXN];
int node_values[MAXN];
int violations_count[MAXN];
set<int> violations_set[MAXN];
set<int> query_nodes;
int level[MAXN];
vector<int> queries[MAXN];
vector<int> query_nodes_vec;
vector<int> result[MAXN];
bool is_violated[MAXN];
map<int, set<int>> violations;
 
void dfs(int node, int parent, int min_val, int max_val, int lvl) {
    level[node] = lvl;
    if (!(min_val < node_values[node] && node_values[node] < max_val)) {
        is_violated[node] = true;
        violations_set[node].insert(node);
        violations_count[node] = 1;
    } else {
        violations_count[node] = 0;
    }
    for (auto &[child, direction] : tree[node]) {
        if (child == parent) continue;
        if (direction == 'l') {
            dfs(child, node, min_val, min(max_val, node_values[node]), lvl + 1);
        } else {
            dfs(child, node, max(min_val, node_values[node]), max_val, lvl + 1);
        }
         if (violations_set[child].size() > violations_set[node].size()) {
            swap(violations_set[node], violations_set[child]);
        }
        violations_set[node].insert(violations_set[child].begin(), violations_set[child].end());
        violations_count[node] += violations_count[child];
    }
    if (query_nodes.find(node) != query_nodes.end()) {
        violations[node] = violations_set[node];
    }
}
 
int main() {
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> node_values[i];
    }
    for (int i = 0; i < N - 1; i++) {
        int u, v;
        char dir;
        cin >> u >> v >> dir;
        u--; v--;
        tree[u].emplace_back(v, dir);
        tree[v].emplace_back(u, dir);
    }
    int Q;
    cin>>Q;
    for (int i = 0; i < Q; i++) {
        int x; cin>>x; x--;
        query_nodes.insert(x);
        query_nodes_vec.push_back(x);
    }
    dfs(0, -1, INT_MIN, INT_MAX, 0);
 
    for(auto node:query_nodes_vec){
        cout<<node+1<<" ";
        if (violations[node].empty()) {
            cout << -1;
        } else {
            for (int v : violations[node]) {
                cout << v + 1 << " ";
            }
        }
        cout<<endl;
    }
 
    for (int i = 0; i < N; i++) {
        cout << violations_count[i]<< " ";
    }
    cout << endl;
    return 0;
}

Problem I

Code

#include<bits/stdc++.h>
using namespace std;

struct Node {
    int count;
    array<int,2>child;
    Node() {
        count = child[0] = child[1] = 0;
    }
};

struct Trie {
    vector<Node>tree;

    Trie() {
        tree.assign(1, Node());
    }

    void insert(int node, int index, array<int,32>&bits) {
        if(index == 31) {
            tree[node].count++;
            return;
        }

        if(!tree[node].child[bits[index + 1]]) {
            tree[node].child[bits[index + 1]] = tree.size();
            tree.push_back(Node());
        }
        
        insert(tree[node].child[bits[index + 1]], index + 1, bits);

        tree[node].count =  (tree[node].child[0] ? tree[tree[node].child[0]].count : 0) + 
                            (tree[node].child[1] ? tree[tree[node].child[1]].count : 0);
    }

    long long query(int node, vector<int>&intended, array<int, 32>&real, int matches = 1) {
        int iterations = (intended.size()) / 2;
        for(int i = 0; i < iterations; i++) {
            int bitOne = (intended[i * 2 + 1] ^ real[i * 2 + 1]);
            int bitTwo = (intended[i * 2] ^ real[i * 2]);

            if(!tree[node].child[bitOne]) return 0;
            node = tree[node].child[bitOne];

            if(!tree[node].child[bitTwo]) return 0;
            node = tree[node].child[bitTwo];

            matches = (matches && (bitOne == real[i * 2]) && (bitTwo == real[i * 2 + 1]));
        }  

        return tree[node].count - matches;
    }
};

const pair<int,int>iter[] = {
    {1, 1}, 
    {1, 0}, 
    {0, 1}, 
    {0, 0},
};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    auto create = [&](vector<int>&a) -> vector<array<int,32>> {
        vector<array<int,32>>arr;
        for(auto &x : a) {
            array<int,32>temp; temp[31] = 0;
            for(int i = 0; i <= 30; i++) {
                temp[i] = (((1 << i) & x) != 0);
            }
            reverse(temp.begin(), temp.end());
            arr.push_back(temp);
        } 
        return arr;
    };

    int tt; cin >> tt;

    while(tt--) {
        long long n, k, cnt = 0, answer = 0; cin >> n >> k;
        vector<int>a(n);
        for(auto &i : a) cin >> i;
        vector<array<int,32>>arr = create(a);
        vector<int>current;
        Trie trie = Trie();
        for(auto &x : arr) trie.insert(0, -1, x);

        for(int i = 0; i <= 30; i += 2) {
            vector<long long>counter(4);

            for(auto &x : arr) {
                for(int itr = 0; itr < 4; itr++) {
                    current.push_back(iter[itr].first); current.push_back(iter[itr].second);
                    counter[itr] += trie.query(0, current, x);
                    current.pop_back(), current.pop_back();
                }
            }

            for(int j = 3; j >= 0; j--) {
                if(cnt + counter[j] >= k) {
                    current.push_back(iter[j].first);
                    current.push_back(iter[j].second);
                    answer = (answer << 2ll) + (iter[j].first * 2ll) + (iter[j].second); 
                    break;
                } else cnt += counter[j];
            }
        }

        cout << answer << "\n";
    }
}

Problem J

Problem K

As in the problem statement, let $$$a_i$$$ be the $$$a_i$$$-th capital English letter.

Consider counting conforming strings for each number of occurrences of $$$z$$$, and finding the answer as their sum. (For convenience we take a letter $$$z$$$, but this is not essential; you can fix any letter and find the count for each number of its occurrences.)

Suppose that a length-$$$s$$$ string has $$$t$$$ occurrences of $$$z$$$. Then, there are $$$\binom{s}{t}$$$ ways to determine the positions of $$$z$$$. The characters at the other positions form a string of length $$$(s−t)$$$ without $$$z$$$ such that $$$a_i$$$ occurs between $$$0$$$ and $$$C_i$$$ times, which is understood by considering the string of length $$$(s−t)$$$ obtained by removing $$$z$$$, for each of the $$$\binom{s}{t}$$$ positions.

Therefore, the problem for $$$a, b, \ldots, z$$$ has been boiled down to that for $$$a, b, \ldots, y$$$.

Similarly, the problem for $$$a, b, \ldots, y$$$ can be boiled down to that for $$$a, b, \ldots, x$$$; repeating this procedure seems to solve the problem.

Once you boiled down the problem with a smaller one, employing DP (Dynamic Programming) is often effective.

Indeed, let $$$dp_{i,j}$$$ be the number of length-$$$j$$$ strings consisting of $$$a_1,a_2,\ldots,a_i$$$ such that $$$a_k$$$ occurs between $$$0$$$ and $$$C_k$$$ times for all $$$1\le k\le i$$$; then by the observation above it turns out that

$$$ dp_{i+1,j} = \sum_{k=0}^{\min(j, C_{i+1})} dp_{i,j−k} \cdot \binom{j}{k} $$$

(We find the sum over $$$k$$$, the number of occurrences of $$$a_{i+1}$$$.)

The answer is

$$$ \sum_{j=1}^{K} dp_{26,j} $$$

Note that the DP only ranges in $$$j\le K$$$.

By finding the binomial coefficients according to precalculated factorials and its inverses, or by precomputing the binomial coefficients themselves in the manner of Pascal’s triangle, this DP can be solved in a total of

$$$ O(\sigma K^2) $$$

time, where $$$\sigma$$$ is the size of alphabet ($$$\sigma=26$$$ in our case), which is fast enough for the constraints for this problem.

Code

const int MAXN = 1001;
const int MOD = 998244353;
int fac[MAXN + 1];
int inv[MAXN + 1];
int exp(int x,int n,int m){x%=m;int res = 1; while(n>0){if(n%2==1){res=res*x%m;}x=x*x%m;n/=2;}return res;}
void factorial(){fac[0]=1;for(int i = 1; i <= MAXN; i++) { fac[i] = fac[i - 1] * i % MOD; }}
void inverses() {inv[MAXN] = exp(fac[MAXN], MOD - 2, MOD);for (int i = MAXN; i >= 1; i--) { inv[i - 1] = inv[i] * i % MOD; }}
int choose(int n, int r) { if(r>n)return 0ll;return (fac[n] * inv[r] % MOD * inv[n - r] % MOD)%MOD;}
 
int div(int a,int b,int m){
    return ((a%m)*(exp(b,m-2,m)%m))%m ;
}
 
int32_t main()
{
    factorial();
    inverses();
    int k;cin>>k;
    vi freq(27,0);
    for(int i=1;i<=26;i++){
        cin>>freq[i];
    }
    vector<vi>dp(27,vi(k+1,0));
    for(int i=1;i<=26;i++){
        dp[i][0]=1;
    }
    for(int j=1;j<=min(freq[1],k);j++){
        dp[1][j]=1;
    }
    for(int i=2;i<=26;i++){
        for(int j=1;j<=k;j++){
            for(int prev=0;prev<=j;prev++){
                int rem=j-prev;
                if(freq[i]>=rem)
                dp[i][j]=(dp[i][j]+(dp[i-1][prev]*choose(j,prev))%mod1)%mod1;
            }
        }
    }

    int sum=0;
    for(int len=1;len<=k;len++){
        sum=(sum+dp[26][len])%mod1;
    }
    cout<<sum<<endl;
    return 0;
}

Problem L