On selecting a substring of length $$$n$$$ from $$$p = s + s$$$, we get a cyclic rotation of $$$s$$$. So, the problem is equivalent to counting the number of distinct cyclic shifts of $$$s$$$. The constraints are small enough to allow bruteforce method of forming all cyclic shifts of $$$s$$$ and deleting the equal ones after sorting them. Time complexity : $$$O(n^2$$$log$$$n)$$$.

Bonus task: Try solving the problem for $$$n \leq 10^6$$$.

#include<bits/stdc++.h>

using namespace std;

#define all(x) begin(x), end(x)
#define sz(x) static_cast<int>((x).size())


int main() {

        ios::sync_with_stdio(0);
        cin.tie(0);

        int t;
        cin >> t;

        while (t--) {

                int n;
                cin >> n;
                string s;
                cin >> s;
                vector<string> v;
                
                for (int i = 0; i < n; i++) {
                        v.push_back(s);
                        s = s.substr(1) + s.substr(0, 1);
                }

                sort(all(v));
                v.erase(unique(all(v)), v.end());     

                cout << sz(v) << "\n";

        }  
}

The main idea is to precompute the answer for every size $$$k$$$ and answer it during the queries using binary search.

We have the following cases to handle then.

For $$$k > 2$$$, there can be 4 ways to select the subset of army:

$$$1.$$$ Select any subarray of size $$$k$$$.

$$$2.$$$ Select any prefix and any suffix, such that the sum of them is $$$k$$$.

$$$3.$$$ Select any prefix of length $$$k-1$$$, and any one extra index.

$$$4.$$$ Select any suffix of length $$$k-1$$$, and any one extra index.

For $$$k=2$$$, we can have the top 2 maximum strength soldiers.

Now since we have different cases for $$$k > 2$$$ and $$$k = 2$$$ it can happen that our precomputed array is not monotonically increasing. To fix this we can have prefix max array which will make the array monotonically increasing.

After precomputing the array, we can answer the queries using binary search.

Time Complexity: $$$O(n^2+ m\log{n})$$$

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define endl '\n'
 
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    int a[n], b[m];
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    for(int i = 0; i < m; i++){
        cin >> b[i];
    }
    int dp[n + 1];
    int prefix[n + 1];
    fill(dp, dp + n + 1, 0);
    fill(prefix, prefix + n + 1, 0);
    for(int i = 0; i < n; i++){
        prefix[i + 1] = prefix[i] + a[i];
    }
 
    // Case 1
    for(int l = 0; l < n; l++){
        for(int r = l + 1; r <= n; r++){
            int s = prefix[r] - prefix[l];
            dp[r - l] = max(dp[r - l], s);
        }
    }
 
    // Case 2
    for(int i = 0; i < n; i++){
        int s = prefix[i] + *max_element(a + i, a + n);
        dp[i + 1] = max(dp[i + 1], s);
    }
 
    // Case 3
    for(int i = 1; i <= n; i++){
        int s = *max_element(a, a + i) + prefix[n] - prefix[i];
        dp[n - i + 1] = max(dp[n - i + 1], s);
    }
 
    // Case 4
    for(int l = 0; l < n; l++){
        for(int r = l + 1; r <= n; r++){
            int s = prefix[l] + prefix[n] - prefix[r];
            dp[l + n - r] = max(dp[l + n - r], s);
        }
    }
 
 
    // case 5
    if (n > 1)
    {
        sort(a, a + n);
        dp[2] = max(dp[2], a[n - 1] + a[n - 2]);
    }
    
    for (int i = 1; i <= n; i++)
    {
        dp[i] = max(dp[i], dp[i - 1]);
    }
 
    // solve
    for(int i = 0; i < m; i++){
        int ans = lower_bound(dp, dp + n + 1, b[i]) - dp;
        if(ans == n + 1){
            cout << -1 << " ";
        }else{
            cout << ans << " ";
        }
    }
    cout << endl;
    return 0;
}

Consider the tree rooted at $$$1$$$.

Claim 1: Consider any node $$$c$$$ for which size of subtree $$$S$$$ of $$$c$$$ $$$\geq$$$ $$$k$$$ and size of all its children subtrees is $$$<k$$$. Let $$$p$$$ be the parent of $$$c$$$. Then there exists an optimal solution in which the edge {$$$p,c$$$} is cut.

Proof: We prove this using exchange argument. Suppose $$$c$$$ and $$$p$$$ are both in the same part say $$$T_1$$$. Cut $$$T_1$$$ along the edge {$$$c,p$$$} to obtain $$$T_1^{'}$$$ and $$$T_1^{"}$$$ and $$$c \in\ T_1^{'}$$$. If $$$T_1^{'}$$$ is good, this step does not reduce the number of good trees, so assume $$$|T_1^{'}|$$$ is not good. Thus number of good trees reduce by atmost $$$1$$$. Suppose $$$T_2,T_3,....,T_l$$$ were the other parts obtained from $$$T$$$ by cutting the edges in $$$S$$$ and which only consist of nodes in $$$S$$$. Thus $$$T_1^{'} \cup\ T_2 \cup\ T_3...... \cup\ T_l =S$$$. Undo the cut operations that resulted in $$$T_2,T_3,.......,T_l$$$ to obtain $$$S$$$. Since $$$|T_i|<k$$$ for $$$i>1$$$ by assumption on $$$c$$$, this step would cause no decrease in the number of good trees. Finally go on removing leaves from $$$S$$$ until it contains exactly $$$k$$$ nodes. This step increases the number of good trees by exactly $$$1$$$. Thus you still obtain the optimal answer with this exchange.

Claim 2: Consider any node that satisfies the condition in Claim 1. Then the answer of the problem for $$$T=S$$$ is $$$1$$$.

Proof: Any cut that does not contain $$$c$$$ has size $$$<k$$$. Thus $$$ans$$$ $$$\leq$$$ $$$1$$$. Equality can be achieved by repeatedly removing leaves until only $$$k$$$ nodes remain in $$$T$$$.

Thus using repeated applications of Claim $$$1$$$, we can break $$$T$$$ into number of such subtrees by DFS. The answer is just the number of parts obtained by Claim $$$2$$$.

#include "bits/stdc++.h"
using namespace std;
 
void solve(){

    int n, k; cin >> n >> k;
    vector<vector<int>> adj(n);
    for(int i = 0; i < n-1; i++){
        int x, y; cin >> x >> y;
        x--; y--;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    int res = 0;

    auto dfs = [&](auto &&self, int v, int p) -> int{
        int c = 1;
        for(int child: adj[v]){
            if(child == p) continue;
            int z = self(self, child, v);
            if(z >= k) res++;
            else c += z;
        }
        return c;
    };

    int c = dfs(dfs, 0, -1);
    if(c >= k) res++;

    cout << res << '\n';

}


signed main(){

    ios::sync_with_stdio(0);
    cin.tie(0);

    int t = 1;
    cin >> t;
    while(t--) solve();

}	

Let there be $$$m$$$ strings which contain the input $$$a$$$. WLOG let they be in $$$t_1, \dots, t_m$$$. (i.e. $$$a \in t_i : \forall : 1 \leq i \leq m$$$)

$$$1.$$$ For $$$x \lt 2^{n-1}$$$, $$$a_x = 0$$$. $$$s_x = ({t_1}_x\oplus \dots \oplus {t_m}_x) \oplus ({t_{(m+1)}}_x\oplus \dots \oplus {t_k}_x)$$$ $$$s_x = ({t_{(m+1)}}_x\oplus \dots \oplus {t_k}_x)$$$ Problem is reduced to finding $$$k - m$$$ strings for $$$s_{new} = s[:2^{n-1}]$$$.

$$$2.$$$ For $$$x \geq 2^{n-1}$$$, $$$a_x = 1$$$. $$$s_x = ({t_1}_x\oplus \dots \oplus {t_m}_x) \oplus ({t_{(m+1)}}_x\oplus \dots \oplus {t_k}_x)$$$ $$$\implies s_x = ({t_1}_x\oplus \dots\oplus {t_m}_x) \oplus ({t_{(m+1)}}_{x-2^{n-1}}\oplus \dots \oplus {t_{k+1}}_{x-2^{n-1}})$$$ $$$\implies s_x = ({t_1}_x\oplus \dots\oplus {t_m}_x) \oplus s_{x-2^{n-1}}$$$ $$$\implies s_x \oplus s_{x-2^{n-1}} = ({t_1}_x\oplus \dots \oplus {t_m}_x)$$$ Problem is reduced to finding $$$m$$$ strings for $$$s_{new} = (s[:2^{n-1}] \oplus s[2^{n-1}:])$$$.

Now Since we know how to reduce the problem to smaller subproblems, we can solve it using recursion.

Here $$$\oplus$$$ is the bitwise XOR operation.

Time complexity of this approach is $$$O(n \cdot 2^n)$$$.

Bonus: Try to solve the problem iteratively.

You can also have a look at this

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
 
int truth[1 << 20];
 
pair<int, int> solve(int n, int start, int end, char alpha, vector<string> &exp)
{
    if (n == 0)
    {
        if (truth[start])
        {
            exp.push_back("");
            return make_pair(exp.size() - 1, exp.size());
        }
        return make_pair(exp.size(), exp.size());
    }
    int mid = (start + end) / 2;
    int sub = 1 << (n - 1);
    for (int i = mid; i < end; i++)
    {
        truth[i] ^= truth[i - sub];
    }
    auto p = solve(n - 1, start, mid, alpha + 1, exp);
    auto q = solve(n - 1, mid, end, alpha + 1, exp);
    for (int i = q.first; i < q.second; i++)
    {
        exp[i] += alpha;
    }
    return make_pair(p.first, q.second);
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    string s;
    cin >> s;
    for (int i = 0; i < (1 << n); i++)
    {
        truth[i] = s[i] - '0';
    }
    vector<string> exp;
    solve(n, 0, 1 << n, 'a', exp);
    cout << exp.size() << endl;
    for (int i = 0; i < exp.size(); i++)
    {
        cout << exp[i] << endl;
    }
    return 0;
}

We can solve this using dynamic programming. Let $$$dp[i][j]$$$ denote the minimum time to cover all the nodes in the subtree rooted at node $$$i$$$ (starting and ending at node $$$i$$$) and $$$j$$$ denote the non-empty subset of {Jaggu, Raju, Bheem} such that the set of people who cover some of the above nodes is exactly $$$j$$$. Let $$$c$$$ be some child node of $$$i$$$ and $$$k$$$ denote the non-empty subset of $$$j$$$. Then, the time taken to cover this subtree and return to node $$$i$$$ is:

Here, $$$t_p$$$ denotes the time taken by the $$$p$$$-th person in set $$$k$$$ to traverse the edge $$$(i,c).$$$ We iterate over all possible non-empty subsets $$$k$$$ of $$$j$$$ and take the minimum of them. Then, iterate over all child nodes of $$$i$$$ and add them to $$$dp[i][j]$$$. Sets $$$j$$$ and $$$k$$$ can be easily implemented by bitmasking.

Here, $$$C_i$$$ denotes the set of child nodes of $$$i.$$$ Time Complexity: $$$O(n).$$$

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

#define ll long long
#define vl vector<ll>
#define forl(i, a, b) for(ll i = a; i < b; i++)
#define pub push_back

const ll N = 1e5 + 1;
const ll MX = 1e18;

vector<vl> g(N), dp(N,vl(8));
vector<vector<vl>> w(N,vector<vl>(3));
vl unvisited(N);

void dfs(ll n){
	unvisited[n]=0;
	forl(i,0,g[n].size()){
		ll x=g[n][i];
		if(unvisited[x]){
			dfs(x);
			forl(j,1,8){
				ll t=MX;
				forl(k,1,8){
					if((k|j)==j){
						ll t1=dp[x][k];
						if(k&1) t1+=2*w[n][0][i];
						if(k&2) t1+=2*w[n][1][i];
						if(k&4) t1+=2*w[n][2][i];
						t=min(t,t1);
					}
				}
				dp[n][j]+=t;
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	#endif
	ll t;
	cin>>t;
	while(t--){
		ll n;
		cin>>n;
		forl(i,1,n+1){
			g[i].clear();
			forl(j,0,3) w[i][j].clear();
			forl(j,0,8) dp[i][j]=0;
			unvisited[i]=1;
		}
		forl(i,1,n){
			ll u,v,j,r,b;
			cin>>u>>v>>j>>r>>b;
			g[u].pub(v);
			g[v].pub(u);
			w[u][0].pub(j);
			w[u][1].pub(r);
			w[u][2].pub(b);
			w[v][0].pub(j);
			w[v][1].pub(r);
			w[v][2].pub(b);
		}
		dfs(1);
		cout<<dp[1][7]<<'\n';
	}
}

Any perfect square is of the form $$$p_1^{k_1}p_2^{k_2}...p_m^{k_m}$$$ where $$$k_1,k_2...,k_m$$$ are even integers.

Now lets try to calculate the answer for each suffix $$$[i,n]$$$

One thing that we can observe is $$$LCM(i,j) \leq LCM(i,j+1)$$$, as at each new index added the "max power" of a prime either increases or stays constant. Since $$$a_i \leq 10^6$$$, any max power of prime can increase at most $$$log(a_i)$$$ times.

So for each prime we can find the ranges where it has odd and even "max power", maintain a lazy segment tree, and add $$$1$$$ to the ranges where the prime has odd max power. We can find these ranges by maintaining monotonic stacks (increasing prime powers) for each prime. We can do it for all the primes and at the end the indices/ranges which are 0 are good ending points for subarrays starting at $$$i$$$.

Overall TC : $$$nlog(n)log({a_i})$$$

#include<bits/stdc++.h>

using namespace std;

#define all(x) begin(x), end(x)
#define sz(x) static_cast<int>((x).size())
//#define int long long

const int INF = 1e8;

struct lazy {
        int min, freq;
        int lazyy;
};

struct SegtreeLazy {
        int size;
        vector<lazy> val;
        void init (int n) {
                size = 1;
                while (size < n) size *= 2;
                val.resize (2 * size - 1);
        }
        
        lazy merge (int x, int y) {
                if (val[x].min == val[y].min) return {val[x].min, val[x].freq + val[y].freq, 0};
                if (val[x].min < val[y].min) return {val[x].min, val[x].freq, 0};
                return {val[y].min, val[y].freq, 0};
        }
        void propagate (int x) {
                val[2 * x + 1].min += val[x].lazyy;
                val[2 * x + 2].min += val[x].lazyy;
                val[2 * x + 1].lazyy += val[x].lazyy;
                val[2 * x + 2].lazyy += val[x].lazyy;
                val[x].lazyy = 0;
        } 

        void build (vector<int> &a, int x, int lx, int rx) {
                if (rx - lx == 1) {
                        if (lx < sz(a)) val[x] = {a[lx], 1, 0};
                        else val[x] = {INF, 1, 0};
                        return;
                }
                int m = (lx + rx) / 2;
                build (a, 2 * x + 1, lx, m);
                build (a, 2 * x + 2, m, rx);
                val[x] = merge (2 * x + 1, 2 * x + 2);
        }

        void build (vector<int> &a) {
                build (a, 0, 0, size);
        }
        
        void RangeUpdate (int l, int r, int x, int lx, int rx, int v) {
                if (rx - lx == 1) {
                        val[x].min += v;
                        return;
                }
                if (lx >= l && rx <= r) {
                        val[x].min += v;
                        val[x].lazyy += v;
                        return;
                }
                propagate (x);
                int m = (lx + rx) / 2;
                if (m > l) {
                        RangeUpdate (l, r, 2 * x + 1, lx, m, v);
                }
                if (m < r) {
                        RangeUpdate (l, r, 2 * x + 2, m, rx, v);
                }
                val[x] = merge (2 * x + 1, 2 * x + 2);
                
        }

        void update (int l, int r, int v) {
                RangeUpdate (l, r, 0, 0, size, v);
        }

        array<int, 2> get (int l, int r, int x, int lx, int rx) {
                if (rx - lx == 1) {
                        return {val[x].min, val[x].freq};
                }
                if (lx >= l && rx <= r) {
                        return {val[x].min, val[x].freq};
                }
                int m = (lx + rx) / 2;
                propagate (x);
                array<int, 2> a1 = {INF, 0}, a2 = {INF, 0};

                if (m > l) {
                        a1 = get(l, r, 2 * x + 1, lx, m);
                }
                if (m < r) {
                        a2 = get(l, r, 2 * x + 2, m, rx);
                }
                if (a1[0] == a2[0]) return {a1[0], a1[1] + a2[1]};
                if (a1[0] < a2[0]) return {a1[0], a1[1]};
                return {a2[0], a2[1]};
        }

        array<int, 2> get (int l, int r) {    
                return get (l, r, 0, 0, size);
        }

        void out () {                
                for (int i = 0; i < sz(val); i++) cout << val[i].min << " " << val[i].freq << " " << val[i].lazyy << "  ";
        }


}; 

const int maxn = 1e6 + 1;
int maxdiv[maxn];

void upd (int x, int i, vector<array<int, 2>> &v, SegtreeLazy &seg) {
        while (sz(v)) {
                auto [y, j] = v.back();
                if (y > x) break;
                v.pop_back();
                auto [_, k] = v.back();
                if (y & 1) seg.update(k + 1, j + 1, -1); 
        }
        auto [_, k] = v.back();
        v.push_back({x, i});
        if (x & 1) seg.update(k + 1, i + 1, 1); 
}


signed main() {

        ios::sync_with_stdio(0);
        cin.tie(0);

        for (int i = 2; i < maxn; i++) {
                if (maxdiv[i]) continue;
                for (int j = i; j < maxn; j += i) maxdiv[j] = i;
        }

        int n;
        cin >> n;

        int a[n];
        for (int i = 0; i < n; i++) cin >> a[i];

        SegtreeLazy seg;
        vector<array<int, 2>> v[maxn];
        for (int i = 0; i < maxn; i++) {
                v[i].push_back({INF, -1});
        }
        seg.init(n);
        vector<int> temp(n, 0);
        seg.build(temp);

        long long ans = 0;
        int i = -1;
        for (auto u : a) {
                i++;
                int cur = -1, c = 0;
                while (u > 1) {
                        int x = maxdiv[u];
                        if (x != cur) {
                                if (c) upd(c, i, v[cur], seg);
                                c = 1;
                                cur = x;
                        }
                        else c++;
                        u /= x;
                }
                if (c) upd(c, i, v[cur], seg);
                auto [mn, cn] = seg.get(0, i + 1);
                if (mn == 0) ans += cn;
        }

        cout << ans;
        
}