07-08 10:05 已编辑下北泽大学沼气动力学院算法工程师发布于新疆

关注

出题组题解

出题人&题解编写人：@itoshiki_Treap,@Umiyuri,@Vsg21,@wensy宝宝要天天开心喔（按字典序排序）

验题人身份暂不公开，因为比赛锅了，我对不起他们。

A 若赠魂灵我胸膛

题目描述：

构造一棵有 $n$ 个节点的树，使得序号为 $1$ 的节点到剩余所有节点的距离之和为 $\frac{(\sqrt{n - 1} + 1) \times (n - 1)}{2}$ 。

解题思路：

假设距离之和为 $x$ ，即 $\frac{(\sqrt{n - 1} + 1) \times (n - 1)}{2} = x$ 。

不难发现如果 $n - 1$ 不是平方数，那么 $x$ 一定取不到整数，此时无解，输出 $-1$ 。

接下来我们对 $\frac{(\sqrt{n - 1} + 1) \times (n - 1)}{2} = x$ 进行化简：

换元，令 $t = \sqrt{n - 1}$ ，

$\frac{(t + 1) \times t^2}{2} = x$ ，

$t \times \sum^{t}_{i = 1}{i} = x$ 。

很显然，我们令 $1$ 为根节点，只需要构造一棵深度为 $t + 1$ 并且每层都有 $t$ 个节点的树即可，总节点数为 $t^2 + 1 = n$ 。

时间复杂度 $O(\sum n)$ 。

AC代码：

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

void solve() {
    int n;
    cin >> n;
    int m = sqrt(n - 1);
    if (m * m == n - 1) {
        cout << n - 1 << "\n";
        int t = 1;
        vector<vector<int>> ans(m, vector<int>(1, 1));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m; j++) {
                ans[i].push_back(++t);
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m; j++) {
                cout << ans[i][j] << " " << ans[i][j + 1] << "\n";
            }
        }
    } else {
        cout << -1 << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int _ = 1;
    cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

B 年华暗换莫惆怅

题目描述：

给定两个相交圆的圆心坐标及半径，要求计算两圆相交区域的面积与该区域内最大内切圆面积的差值。

其中，两圆的位置由各自的圆心坐标（二维平面坐标）和半径确定。

相交区域的最大内切圆指的是能完全包含于两圆交集内的面积最大的圆。

解题思路：

两圆的位置关系（设圆心距离为 $d$ ，圆的半径分别为 $r_1,r_2$ ：

外离： $d > r_1 + r_2$

外切： $d = r_1 + r_2$

相交： $|r_1 - r_2| < d < r_1 + r_2$

内切： $d = |r_1 - r_2|$

内含： $d < |r_1 - r_2|$

题意已经保证两个圆的关系是：外切、相交或内切，当然，还有极为特殊的情况，那就是重合。

alt

$a_1,a_2$ 为图中标注的角， $b_1,b_2$ 为这两个角的二倍角。

内切圆的知直径为两圆半径之和减去圆心距。

用余弦定理得到 $a_1,a_2$ ，这一步之前可以进行特判，因为如果圆心距 $d$ 为 $0$ 即两圆重合时，余弦定理的分母上会有 $0$ 。

由正弦定理和扇形面积公式，所求面积 $S = \frac{r_1^2 \times b_1}{2} - \frac{r_1^2 \times sin{b_1}}{2} + \frac{r_2^2 \times b_2}{2} - \frac{r_2^2 \times sin{b_2}}{2}$ 。

时间复杂度 $O(T)$ 。

AC代码：

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

void solve() {
    double x1, y1, r1, x2, y2, r2;
    cin >> x1 >> y1 >> r1 >> x2 >> y2 >> r2;
    double d = hypot(x1 - x2, y1 - y2);
    if (d == 0) {
        cout << 0 << "\n";
        return;
    }
    double r0 = (r1 + r2 - d) / 2.0;
    double a1 = (r1 * r1 + d * d - r2 * r2) / (2.0 * r1 * d);
    double a2 = (r2 * r2 + d * d - r1 * r1) / (2.0 * r2 * d);
    double b1 = 2.0 * acos(a1), b2 = 2.0 * acos(a2);
    double S = 0.5 * (r1 * r1 * (b1 - sin(b1)) + r2 * r2 * (b2 - sin(b2)));
    cout << max(S - M_PI * r0 * r0, 0.0) << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int _ = 1;
    cin >> _;
    cout << fixed << setprecision(0);
    while (_--) {
        solve();
    }
    return 0;
}

C 伊菲的打猎

题目描述：

给定一个时间点，有下列 $3$ 种限制：

(1) 星期：星期一到星期五的 $13:30$ 到 $23:59$ 合法，星期六与星期日的 $12:00$ 到 $23:59$ 合法。

(2) 日期：每个月的 $10$ 号与 $20$ 号一定不合法。

(3) 年份：只有今年的时间合法。

这个时间点是否合法，不合法则输出最近且字典序最小的合法时间点。

解题思路：

首先可以根据今年不是闰年，且 $6$ 月 $14$ 日是星期六这点推出每天是星期几。

那么判断一个星期合法的只需要判断今天是否在题面所给的同一年，是不是 $10$ 号或者 $20$ 号，然后接着判断日期，最后是时间点是否满足是当天合法时间。

维护两个时间点指针，一个往前一个往后，判断合法直接返回时间点即可。

AC代码：

#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
#define int long long
const int N=2e5+10;
const int M=1e6+10;
int sx[14]={1145141919810,31,28,31,30,31,30,31,31,30,31,30,31,1145141919810};
map<pair<int,int>,int>mp;
void sjj(int& a,int& b,int&c,int&d){
    d+=1;
    if(d==60){
        d=0;
        c++;
    }
    if(c==24){
        c=0;
        b++;
    }
    if(b>sx[a]){
        b=1;
        a++;
    }
}
void sjja(int& a,int& b,int&c,int&d){
    d--;
    if(d==-1){
        d=59;
        c--;
    }
    if(c==-1){
        c=23;
        b--;
    }
    if(b==0){
        b=sx[--a];
    }
}
void sjjat(int&a,int&b,int&c){
    int bh;
    if(b==10||b==20)bh=0;
    else if(c==6||c==7)bh=1;
    else bh=2;
    mp[{a,b}]=bh;
    b++;
    if(b>sx[a]){
        b=1;
        a++;
    }
    c++;
    if(c==8)c=1;
}
void sjjt(int&a,int&b,int&c){
    int bh;
    if(b==10||b==20)bh=0;
    else if(c==6||c==7)bh=1;
    else bh=2;
    mp[{a,b}]=bh;
    b--;
    if(b==0){
        b=sx[--a];
    }
    c--;
    if(c==0)c=7;
}
bool hf(int a,int b,int c,int d){
    if(mp.count({a,b})==0)return 0;
    int zt=mp[{a,b}];
    if(zt==0)return 0;
    if(zt==1)return c>=12;
    return ((c==13&&d>=30)||c>13);
}
void solve(){
    int a,b,c,d;
    string s;
    cin>>a>>b>>s;
    c=s[0]*10+s[1]-11*'0';
    d=s[3]*10+s[4]-11*'0';
    int xa=6,xb=14,xc=6;
    while(xa<13)sjjat(xa,xb,xc);
    xa=6,xb=14,xc=6;
    while(xa)sjjt(xa,xb,xc);
    int ya=a,yb=b,yc=c,yd=d;
    if(hf(a,b,c,d)){
        cout<<"YES\n";
        return;
    }
    cout<<"NO\n";
    while(1){
        if(hf(a,b,c,d)||hf(ya,yb,yc,yd)){
            if(hf(a,b,c,d)){
                cout<<a<<" "<<b<<" ";
                if(c<=9)cout<<"0";
                cout<<c;
                cout<<":";
                if(d<=9)cout<<"0";
                cout<<d<<"\n";
            }
            else{
                cout<<ya<<" "<<yb<<" ";
                if(yc<=9)cout<<"0";
                cout<<yc;
                cout<<":";
                if(yd<=9)cout<<"0";
                cout<<yd<<"\n";
            }
            return;
        }
        sjj(ya,yb,yc,yd);
        sjja(a,b,c,d);
    }
}
signed main(){
    ios::sync_with_stdio(0);cout.tie(0);cin.tie(0);
    solve();
}

D 用户彻底怒了。

简要题意：

构造两个长度不超过 $3\times 10^5$ 的数列，使得它们合并后是一个排列，且它们的前 $k(k\le 17)$ 次方和都相等。

题解：

构造方法： $k=0$ 时令 $A=\{1\},B=\{2\}$ 。

否则，令 $+$ 为两个数列的拼接，先递归求出 $k-1$ 时的 $A,B$ ，记为 $A^{*},B^{*}$ ；

令 $A=A^{*}+\{B^{*}_i+2^k\}$ ， $B=B^{*}+\{A^{*}_i+2^k\}$ 即可。

时间复杂度 $\Theta(k2^k)$ 。

对性质的证明：

首先对于 $\forall j\in[0,k]$ ， $\sum_{i=1}^{n}a_{i}^{j}=\sum_{i=1}^{n}b_{i}^{j}$ ,我们数学归纳证明。

归纳起点为 $k=0$ ，此时显然满足。

考虑假设 $k=m$ 时满足，那么对于 $k=m+1$ ，我们即证：

$\forall j\in[0,m+1]，\sum_{i=1}^{2^m}(A^{*}_{i})^j+\sum_{i=1}^{2^m}(B^{*}_{i}+2^{m+1})^j=\sum_{i=1}^{2^m}(B^{*}_{i})^j+\sum_{i=1}^{2^m}(A^{*}_{i}+2^{m+1})^j$ 。

用二项式定理拆开 $(A^{*}_{i}+2^{m+1})^j$ ：

(A^{*}_{i}+2^{m+1})^j\\=\sum_{p=0}^{j}\binom{j}{p}(A^{*}_i)^p(2^{m+1})^{j-p}

同理：

(B^{*}_{i}+2^{m+1})^j\\=\sum_{p=0}^{j}\binom{j}{p}(B^{*}_i)^p(2^{m+1})^{j-p}

对于每一组相同的 $p$ ，对 $i$ 求和，有：

\sum_{i=1}^{2^m}\binom{j}{p}(A^{*}_i)^p(2^{m+1})^{j-p}

=\binom{j}{p} (2^{m+1})^{j-p}\sum_{i=1}^{2^m}(A^{*}_i)^p

以及：

\sum_{i=1}^{2^m}\binom{j}{p}(B^{*}_i)^p(2^{m+1})^{j-p}

=\binom{j}{p} (2^{m+1})^{j-p}\sum_{i=1}^{2^m}(B^{*}_i)^p

由归纳假设：

$\forall p\in[0,m],\sum_{i=1}^{2^m}(A^{*}_i)^p=\sum_{i=1}^{2^m}(B^{*}_i)^p$

容易发现对于 $j\in[0,m]$ 都成立，则证原等式即证：

$\sum_{i=1}^{2^m}(A^{*}_{i})^{m+1}+\sum_{i=1}^{2^m}(B^{*}_{i}+2^{m+1})^{m+1}=\sum_{i=1}^{2^m}(B^{*}_{i})^{m+1}+\sum_{i=1}^{2^m}(A^{*}_{i}+2^{m+1})^{m+1}$

由

(A^{*}_{i}+2^{m+1})^{m+1}\\=\sum_{p=0}^{m+1}\binom{m+1}{p}(A^{*}_i)^p(2^{m+1})^{m+1-p}

则显然有：

$\forall p\in[0,m]，\binom{m+1}{p}(2^{m+1})^{m+1-p}\sum_{i=1}^{2^m}(A^{*}_i)^p=\binom{m+1}{p}(2^{m+1})^{m+1-p}\sum_{i=1}^{2^m}(B^{*}_i)^p$

即证：

$\sum_{i=1}^{2^m}(A^{*}_{i})^{m+1}+\binom{m+1}{m+1}(2^{m+1})^{m+1-m-1} \sum_{i=1}^{2^m}(B^{*}_i)^{m+1}=\sum_{i=1}^{2^m}(B^{*}_{i})^{m+1}+\binom{m+1}{m+1}(2^{m+1})^{m+1-m-1} \sum_{i=1}^{2^m}(A^{*}_i)^{m+1}$

该式子显然成立，因此原式得证，该性质得到证明。

之后，归纳证明排列性质：

显然 $k=0$ 时构成排列 $\{1,2\}$ ，长度为 $2^{k+1}$ ；

之后，考虑 $k=n$ 时若构成一个长度为 $2^{n+1}$ 的排列，整个构造过程本质上等价于将排列复制一份后，将复制的部分整体加上 $2^{n+1}$ ，相当于将一个长度为 $2^{n+1}$ 的排列向后平移了 $2^{n+1}$ ，显然与自身构成一个长度 $2^{n+2}$ 的排列，得证。

AC代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    auto solve=[&](auto &&self,int k)->pair<vector<int>,vector<int>>
    {
        if(k==0) return {{1},{2}};
        auto [rA,rB]=self(self,k-1);
        auto retA=rA,retB=rB;
        for(auto x:rB) retA.push_back(x+(1ll<<k));
        for(auto x:rA) retB.push_back(x+(1ll<<k));
        return {retA,retB};
    };
    int k;cin>>k;
    auto [a,b]=solve(solve,k);
    cout<<a.size()<<endl;
    for(auto x:a) cout<<x<<' ';cout<<endl;
    for(auto x:b) cout<<x<<' ';cout<<endl;
    return 0;
}

E 古掌计奇人

简要题意：

给定长度为 $n+1$ 的正整数数列 $\{A_i\}$ 和长度为 $n$ 的正整数数列 $\{B_i\}$ ，两个数列的下标都从 $0$ 开始。还有一个正整数集合 $S$ ，初始为空。

你可以执行两种操作：

选择一个不在集合里且满足 $A_0\gt A_i$ 的下标 $i$ ，令 $A_i \leftarrow 0$ ，并将 $i$ 加入集合。
设集合当前大小为 $|S|$ ，支付 $B_{|S|}$ 的代价，使得 $\forall j \in \{0\}\cup{S}，A_j \leftarrow A_j+1$ 。对于在 $S$ 中的 $j$ ，若本次操作后 $A_j$ 达到初始值，则自动将 $j$ 移出 $S$ 。

求最小的总代价，使得 $S=\{i|i \in[1,n]\}$ ，也就是从 $1$ 到 $n$ 的所有下标都在集合 $S$ 中。

题解：

假设我们现在最多可以击倒 $k$ 个小黑，注意到我们可以用以下策略把被击倒的小黑数量固定在一个不超过 $k$ 的数：

先击倒我们想要的数量的小黑，之后进行购买时，一旦有小黑恢复力量，我们立刻将其重新击倒，显然因为小黑恢复力量的时候我们也在提升相同数量的力量，并且小黑的力量最大只能回到原来的力量值，因此一旦有一个小黑被击倒过一次，后续就可以无限次被击倒。

因此，对于 $p\in[0,k]$ ，我们一定可以把代价固定到 $\min \{B_p\}$ 上。显然随着力量的提升， $k$ 会单调不下降，因此最优策略一定是选择前缀最小值作为当前的代价。

直接排序后模拟即可，时间复杂度 $\Theta(n\log n)$ ，瓶颈在排序。

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+11;
using ll=long long;
void solve()
{
    int n;cin>>n;
    ll pa;cin>>pa;
    vector<ll> a(n+3,0),b(n+3,0);
    for(int i=1;i<=n;++i) cin>>a[i];
    for(int i=0;i<n;++i) cin>>b[i];
    ll ans=0;int ip=0;
    sort(a.begin()+1,a.begin()+n+1);
    ll avl=b[0];
    for(ip=1;ip<=n;++ip) if(a[ip]>=pa) break;
    for(int i=1;i<ip;++i) avl=min(avl,b[i]);
    for(int i=ip;i<=n;++i)
    {
        ll dlt=(a[i]+1-pa);
        pa=a[i]+1;ans+=dlt*avl;
        avl=min(avl,b[i]);
    }
    cout<<ans<<endl;
}
int main()
{
    solve();
    return 0;
}

F 闪回，蝉鸣，再也回不来的你。

简要题意：

给定一张无重边无自环的无向图，问有多少张无重边，无自环的连通二分图满足：这张图删掉一条边后可以得到给定的图。

多测， $n \le 2\times 10^5,m \le 6\times 10^5,\sum n\le 5\times 10^5,\sum m \le 2\times 10^6$ 。

题解：

考虑如果答案不为 $0$ ，给定的图本身一定也是二分图，因此先对所有连通块进行黑白二着色，如果失败，则答案为 $0$ 。

否则，当给定的图只有一个连通块时，考虑二分图的定义，进行黑白二着色后，只需要选择一个黑点和一个白点，在它们之间连边一定仍然得到一张二分图。设黑点有 $a$ 个，白点有 $b$ 个，则答案为 $a\times b-m$ （注意原有的边要减掉）。

当给定的图有两个连通块，且两个连通块都是二分图时，考虑二分图的充要条件是不存在奇环，我们为了让图变成连通图，新加的边必须跨过这两个连通块，这样的边不可能产生任何环。因此，设第一个连通块大小为 $s_1$ ，第二个连通块大小为 $s_2$ ，答案为 $s_1 \times s_2$ 。

否则，显然不能通过只加入一条边就让图变得连通，答案为 $0$ 。

时间复杂度线性。

AC代码：

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve()
{
    int n,m;
    cin>>n>>m;
    vector<vector<int> > G(n+3);
    vector<int> cid(n+3,0),col(n+3,-1);
    int cidcnt=0;
    auto dfs=[&](auto &&self,int u,int _,int _id)->bool
    {
        cid[u]=_id;col[u]=_;
        for(auto v:G[u])
        {
            if(!cid[v])
            {
                if(!self(self,v,1-_,_id)) return 0;
            }
            else if(col[u]==col[v]) return 0;
        }
        return 1;
    };
    for(int i=1,iu,iv;i<=m;++i)
    {
        cin>>iu>>iv;
        G[iu].push_back(iv);
        G[iv].push_back(iu);
    }
    bool ok=1;
    for(int i=1;i<=n;++i) if(!cid[i])
    {
        ok&=dfs(dfs,i,1,++cidcnt);
        if(!ok) break;
        else if(cidcnt>2) break;
    }
    ll ans=0;
    if((!ok)||(cidcnt>2)) ans=0;
    else if(cidcnt==1)
    {
        int cs1=0,cs2=0;
        for(int i=1;i<=n;++i) if(col[i]) ++cs1;else ++cs2;
        ans=1ll*cs1*cs2-m;
    }
    else if(cidcnt==2)
    {
        int cs1=0,cs2=0;
        for(int i=1;i<=n;++i) if(cid[i]==1) ++cs1;else ++cs2;
        ans=1ll*cs1*cs2;
    }
    cout<<ans<<'\n';
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    int t;cin>>t;
    while(t--) solve();
    return 0;
}

G 无名故事 II

简要题意：

设一个长度为 $L$ 的好数列 $\{a_i\}$ 为：一个长度为 $L$ 的自然数数列，满足：

构造一张有向图，点集为所有下标和（数列中所有出现过的值 $+1$ ）的并集，每个点 $i$ 向 $a_i+1$ 连边，得到的图的每个点都在一个环上。

给定一个自然数数列，多次操作，区间加（保证自然数数列性质），区间查询连续子数列是否为好数列。

$n\le 5\times 10^5,m\le 3\times 10^5,a_i\le 5\times 10^5$ 。

题解：

考虑“好数列”的条件的等价描述：将数列所有值向右整体平移 $1$ 后，建立的有向图看成一个每个位置向自身的值的轮换，不难发现这个描述等价于每个点都在一个有向环上，也就是说整张图是若干个置换环。

因此可以推出： $\{b_{i}+1\}$ 构成一个 $[1,L]$ 的排列，也就是好数组一定是一个 $[0,L-1]$ 的排列。

考虑维护：这个东西没什么太好的性质，注意到本质是判断两个集合是否相同，考虑哈希。

一种便于维护数值区间加法的哈希是， $\operatorname{hash}(v)=g^v$ ，其中 $g$ 是我们选取的一个底数，推荐在模数范围内随机选取。

这样，一个序列所对应的集合的哈希值就是 $\sum g^{a_i}$ ，如果要进行区间加修改，即为 $\sum g^{a_i+x}=\sum (g^{a_i}\times g^x)=g^x\times \sum g^{a_i}$ ，也就是哈希值上的区间乘法。

使用线段树维护区间乘区间求和即可，注意处理逆元。

时间复杂度 $\Theta(n\log n)$ ，没有故意卡 $\Theta(n\log ^2 n)$ 的实现。

注意：维护 $\operatorname{hash}(v)=\sum_{i=0}^{k}c_iv^2$ 在 $k\le \log n$ 时很好卡掉，和 $c_i$ 的取值无关，样例二就是用于警告选手的。

AC代码：

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll mod1=1e9+7,mod3=1e9+9;
mt19937 gen(chrono::system_clock::now().time_since_epoch().count());
using uidi=uniform_int_distribution<int>;
const ll _g1=uidi(2,mod1-1)(gen),_g3=uidi(2,mod3-1)(gen);
ll fpm(ll x,ll y,ll md)
{
    ll ret=1;
    for(;y;y>>=1,x=(x*x)%md) if(y&1) ret=(ret*x)%md;
    return ret;
}
ll fpm1(ll y)
{
    if(y<0) return fpm(fpm1(-y),mod1-2,mod1);
    ll ret=1,x=_g1;
    for(;y;y>>=1,x=(x*x)%mod1) if(y&1) ret=(ret*x)%mod1;
    return ret;
}
ll fpm3(ll y)
{
    if(y<0) return fpm(fpm3(-y),mod3-2,mod3);
    ll ret=1,x=_g3;
    for(;y;y>>=1,x=(x*x)%mod3) if(y&1) ret=(ret*x)%mod3;
    return ret;
}
struct info
{
    ll xs1,xs3;ll sum,len;
    info():xs1(0),xs3(0),sum(0),len(1) {}
    info(ll x):xs1(fpm1(x)),xs3(fpm3(x)),sum(x),len(1){}
    info(ll x1,ll x3,ll x,ll _len):xs1(x1),xs3(x3),sum(x),len(_len){}
};
struct tg
{
    ll xs1,xs3;ll sum;
    tg():xs1(1),xs3(1),sum(0){}
    tg(ll x):xs1(fpm1(x)),xs3(fpm3(x)),sum(x){}
    tg(ll x1,ll x3,ll x):xs1(x1),xs3(x3),sum(x){}
    bool _e() {return (xs1==1)&&(xs3==1)&&(sum==0);}
};
info operator + (const info& a,const info& b)
{
    return info((a.xs1+b.xs1)%mod1,(a.xs3+b.xs3)%mod3,a.sum+b.sum,a.len+b.len);
}
tg operator + (const tg& a,const tg& b)
{
    return tg(a.xs1*b.xs1%mod1,a.xs3*b.xs3%mod3,a.sum+b.sum);
}
info operator + (const info &a,const tg &b)
{
    return info(a.xs1*b.xs1%mod1,a.xs3*b.xs3%mod3,a.sum+a.len*b.sum,a.len);
}
bool operator ==(const info& a,const info& b)
{
    return (a.xs1==b.xs1)&&(a.xs3==b.xs3)&&(a.sum==b.sum)&&(a.len==b.len);
}
struct segtree
{
    vector<int> ls,rs;
    vector<info> sum;vector<tg> tag;
    int ct,rt;
    segtree(int _n):ct(0),rt(0)
    {
        ls=rs=vector<int>(2*_n+3,0);
        sum=vector<info>(2*_n+3,info(0,0,0,0));
        tag=vector<tg>(2*_n+3,tg());
    }
    void down(int x)
    {
        if(tag[x]._e()) return;
        tag[ls[x]]=tag[ls[x]]+tag[x];
        tag[rs[x]]=tag[rs[x]]+tag[x];
        sum[ls[x]]=sum[ls[x]]+tag[x];
        sum[rs[x]]=sum[rs[x]]+tag[x];
        tag[x]=tg();
    }
    void up(int x)
    {
        sum[x]=sum[ls[x]]+sum[rs[x]];
    }
    void cst(int &x,int l,int r)
    {
        x=++ct;if(l==r) return;int mid=(l+r)/2;
        cst(ls[x],l,mid);cst(rs[x],mid+1,r);up(x);
    }
    void cst(int &x,int l,int r,vector<ll>& _a)
    {
        x=++ct;if(l==r) {sum[x]=info(_a[l]);return;}
        int mid=(l+r)/2;
        cst(ls[x],l,mid,_a);cst(rs[x],mid+1,r,_a);up(x);
    }
    void add(int x,int l,int r,int al,int ar,tg v)
    {
        if(al<=l&&r<=ar)
        {
            sum[x]=sum[x]+v,tag[x]=tag[x]+v;
            return;
        }
        down(x);int mid=(l+r)/2;
        if(al<=mid) add(ls[x],l,mid,al,ar,v);
        if(mid+1<=ar) add(rs[x],mid+1,r,al,ar,v);up(x);
    }
    info ask(int x,int l,int r,int ql,int qr)
    {
        if(ql<=l&&r<=qr) return sum[x];
        down(x);int mid=(l+r)/2;info ret;ret.len=0;
        if(ql<=mid) ret=ret+ask(ls[x],l,mid,ql,qr);
        if(mid+1<=qr) ret=ret+ask(rs[x],mid+1,r,ql,qr);
        return ret;
    }
};
void solve()
{
    int n,m;
    cin>>n>>m;
    vector<info> pans(n+3);pans[0].len=0;
    for(int i=1;i<=n;++i) pans[i]=pans[i-1]+info(i-1);
    vector<ll> a(n+3,0);
    for(int i=1;i<=n;++i) cin>>a[i];
    segtree sgt(n+1);sgt.cst(sgt.rt,1,n,a);
    for(int i=1,op,il,ir;i<=m;++i)
    {
        cin>>op>>il>>ir;
        if(op==1)
        {
            ll x;cin>>x;
            sgt.add(1,1,n,il,ir,tg(x));
        }
        else
        {
            auto sv=sgt.ask(1,1,n,il,ir);
            if(sv==pans[ir-il+1]) cout<<"DA\n";
            else cout<<"NIE\n";
        }
    }
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    solve();
    return 0;
}

H 你怎么知道我玩原神还是玩刻晴的？

简要题意：

定义一个正整数集合的 $\operatorname{mex^+}+$ 为从 $1$ 开始的最小的没有出现过的正整数。

给定正整数数列 $\{a_i\}$ ，问有多少个连续子数组 $a[l,r]$ 满足这个连续子数组构成的正整数集合的 $\operatorname{mex^+}$ 值与其最大公因数 $\gcd$ 值相等。

题解：

按照和 $\operatorname{mex}$ 相同的套路考虑：先考虑某个连续子数组里是否存在 $1$ 。

如果存在，那么 $\operatorname{mex^+}$ 值一定 $\gt 1$ ，同时其 $\gcd$ 值因为出现了 $1$ 一定等于 $1$ ，因此这样的连续子数组一定不合法。

那么，此时这个连续子数组对应的集合的 $\operatorname{mex^+}$ 值一定等于 $1$ ，此时只需要检查其 $\gcd$ 值是否为 $1$ 即可。

题目转化为：用出现过的 $1$ 将原数列断开为若干个极大连续段，对每个段求有多少个连续子数组的 $\gcd=1$ 。

方法有很多，出题人用的是 ST 表和双指针，时间复杂度 $\Theta(n\log n)$ 。

AC代码：

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
struct stt
{
    vector<vector<int> > a;
    int _n,_lgp;
    stt(int __):_n(__),_lgp(__lg(_n))
    {
        a=vector<vector<int> >(_lgp+1,vector<int>(_n+3,0));
    }
    void init(vector<int> &_a,int _n)
    {
        for(int i=1;i<=_n;++i) a[0][i]=_a[i];
        for(int j=1;j<=_lgp;++j) for(int i=1;i+(1<<j)-1<=_n;++i)
        {
            a[j][i]=gcd(a[j-1][i],a[j-1][i+(1<<(j-1))]);
        }
    }
    int ask(int l,int r)
    {
        int _g=__lg(r-l+1);
        return gcd(a[_g][l],a[_g][r-(1<<_g)+1]);
    }
};
void solve()
{
    int n;cin>>n;
    vector<int> a(n+3,0),vis(n+3,0);stt st(n+3);
    for(int i=1;i<=n;++i) cin>>a[i];
    st.init(a,n);ll ans=0;
    auto sol=[&](int L,int R)->ll
    {
        if(L>R) return 0;
        int rp=L;ll ret=0;
        for(int lp=L;lp<=R;++lp)
        {
            rp=max(rp,lp);
            while(rp+1<=R&&(st.ask(lp,rp)>1)) ++rp;
            //cout<<"CALL: "<<lp<<' '<<rp<<endl;
            if(st.ask(lp,rp)==1) ret+=(R-rp+1);
        }
        return ret;
    };
    for(int i=1;i<=n;++i) if(a[i]==1) vis[i]=1;
    for(int i=1;i<=n;++i)
    {
        if(vis[i]) continue;
        int lp=i;
        while(i+1<=n&&vis[i+1]!=1) ++i;
        int rp=i;ans+=sol(lp,rp);
    }
    cout<<ans<<endl;
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    solve();
    return 0;
}

I 星云桥

简要题意：

给定一棵边带颜色的无根树，求至少存在一对相邻边颜色相同的简单路径数量。

多测， $n\le 2\times 10^5,\sum n \le 10^6,c_i \le 10^6$ 。

题解：

我们这里考虑计算补集，即任意两条相邻边都不同色的路径数量，用所有的简单路径数量 $\frac {n\times(n-1)}{2}$ 减去结果即为答案。

计算补集考虑一个简单的树形 DP：设 $f_{u,col}$ 为以 $u$ 为路径上端点，深度最浅的边颜色为 $col$ 的深度严格单调递增路径（又称直路径）的数量，那么在计算完毕后，设 $s_u=\sum_{i\in \{col\}}f_{u,i}$ ，每种颜色都有 $\frac {f_{u,col}\times (s_u-f_{u,col})}{2}$ 的贡献，同时 $s_u$ 自身也会产生贡献。

至于 DP 的转移，设有根树意义下结点 $u$ 父边颜色为 $cf_u$ ，那么转移方程为 $f_{u,cf_v}=s_v-f_{v,cf_v}(v\in son(u))$ ，由于值域很小，开桶即可线性转移。

时间复杂度线性，注意常数。

也有时间复杂度 $\Theta(n\log n)$ 的点分治做法，很容易被卡，不多引入了。

AC代码：

#include<bits/stdc++.h>
using namespace std;
void syncoff()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
}
#define endl '\n'
const int N=1e6+11;
using ll=long long;
using i128=__int128;
int t,n,k,m,q;
vector<pair<int,int> > G[N];
ll g[N],cdp[N],cnd[N],csum,ans;
bool cvis[N];
void dfs(int u,int f)
{
    ll cssum=0;
    vector<int> scols;
    for(auto [v,col]:G[u])
    {
        if(v==f) continue;
        cnd[v]=col;
        dfs(v,u);
    }
    for(auto [v,col]:G[u])
    {
        if(v==f) continue;
        cdp[col]+=g[v]+1;cssum+=g[v]+1;
        if(!cvis[col]) cvis[col]=1,scols.push_back(col);
    }
    ll pans1=0,pans2=0;
    pans1+=cssum;g[u]+=cssum;g[u]-=cdp[cnd[u]];
    for(auto x:scols) pans2+=cdp[x]*(cssum-cdp[x]);
    for(auto x:scols) cvis[x]=0,cdp[x]=0;cssum=0;
    scols.clear();pans2/=2ll;ans-=(pans1+pans2);
}
void clr()
{
    ans=0;
    for(int i=1;i<=n;++i) g[i]=cnd[i]=0,G[i].clear();
}
void solve()
{
    cin>>n;ans=1ll*n*(n-1)/2ll;
    for(int i=1,iu,iv,ic;i<n;++i)
    {
        cin>>iu>>iv>>ic;
        G[iu].push_back(make_pair(iv,ic));
        G[iv].push_back(make_pair(iu,ic));
    }
    dfs(1,0);cout<<ans<<endl;
    return clr();
}
int main()
{
    syncoff();t=1;
    cin>>t;
    while(t--) solve();
    return 0;
}

J 伊菲的比赛

题目描述：

给一个概率 $\frac{p}{q}$ ，你需要给出 $2n$ 次尝试恰好成功 n 次的概率。

解题思路：

仅看一种情况的概率，成功与不成功分别为 $n$ 次，有： $(\frac{p}{q})^n(1-\frac{p}{q})^n \tag{1}$ 成功与不成功分别为 $n$ 次，总情况个数有： $\binom{2n}{n} \tag{2}$ 总情况个数与每种情况的概率作积有： $\binom{2n}{n}(\frac{p}{q})^n(1-\frac{p}{q})^n \tag{3}$ 计算即可。

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
class Zhs {
private:
    std::vector<int> zh,ny;
    int mod,siz;
    void exgcd(int a,int b,int &x,int &y){
        if(!b){
            x=1,y=0;
            return;
        }
        exgcd(b,a%b,x,y);
        int t=x;
        x=y;
        y=t-y*(a/b);
    }

public:
    Zhs(int si,int m){
        siz=si;
        mod=m;
        zh=ny=vector<int>(siz+1);
        zh[0]=1;
        for(int i=1;i<=siz;i++)zh[i]=(zh[i-1]*i)%mod;
        for(int i=0;i<=siz;i++){
            int x,y;
            exgcd(zh[i],mod,x,y);
            ny[i]=(x%mod+mod)%mod;
        }
    }
    int A(int a) { return zh[a]; }
    int C(int a, int b) {return ((zh[a]*ny[a - b]) % mod)*ny[b]%mod;}
};
const int mod=998244353;
Zhs zhs(2e5+10,998244353);
int qpow(int a,int b){
    int ans=1;
    while(b){
        if(b&1)ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
void solve(){
    int n,p,q;cin>>n>>p>>q;
    cout<<zhs.C(2*n,n)*qpow((p*(q-p)%mod)*qpow(q*q%mod,mod-2)%mod,n)%mod<<'\n';
}
signed main(){
    ios::sync_with_stdio(0);cout.tie(0);cin.tie(0);
    solve();
}

K 爪痕，强颜欢笑，并非是爱的某物。

简要题意：

给定小写字母字符串 $s$ ，要求添加一个长度不超过它自身的前缀，最小化新串的最小循环节长度，输出任意满足条件的解。

最多 $5$ 组多测， $|s|\le 5\times 10^5$ 。

为了方便处理，我们先将字符串翻转，以下解法针对原串的反串。

题解解法一：

考虑字符串的循环节与周期的关系：长度能够整除字符串长度的周期是循环节。

因此，设某个周期为 $k$ ，字符串长度为 $n$ ，当 $k|n$ 时，这个周期是循环节；否则，它不是循环节，需要补充 $k-n\mod k$ 个字符才能使得它成为循环节，而这个循环节的长度直接也是 $k$ 。

注意到 $k-n\mod k$ 这个式子的值一定不会超过 $n$ ，因此可以考虑让最小的周期成为新的循环节。由上面的推论，不可能有更短的答案。

而字符串的所有周期都和它的 $\operatorname{border}$ 一一对应，对应关系是周期长度为 $n-|\operatorname{border}|$ ，因此原串的最长 $\operatorname{border}$ 就对应最小周期。

这一步直接 $\operatorname{KMP}$ 求出即可，也可以枚举长度拿字符串哈希验证。

时间复杂度线性。

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+111;
using ll=long long;
vector<int> getpi(string _s)
{
    int _n=_s.length();vector<int> ret(_n+3,0);
    for(int i=2;i<=_n;++i)
    {
        int _x=ret[i-1];
        while(_x&&_s[_x]!=_s[i-1]) _x=ret[_x];
        if(_s[_x]==_s[i-1]) ++_x;ret[i]=_x;
    }
    return ret;
}
void solve()
{
    string str;
    cin>>str;int n=str.length();reverse(str.begin(),str.end());
    vector<char> ans;for(auto x:str) ans.push_back(x);
    auto xpi=getpi(str);int _=n-xpi[n];
    int m=_;while(m<=n) m+=_;
    for(int i=1;i<=m-n;++i) ans.push_back(ans[i+n%_-1]);
    reverse(ans.begin(),ans.end());
    for(auto x:ans) cout<<x;cout<<endl;
}
int main()
{
    int t;cin>>t;
    while(t--) solve();
    return 0;
}

题解解法二：

考虑到所有可能的循环节一定都是原串的一个前缀，因此我们直接枚举所有前缀，考虑其成为循环节的可能性。

本质上仍然是验证每个长度是否是这个字符串的周期，不过实现方法可以用一个更粗暴的：

我们对于当前长度为 $i$ 的前缀，从头开始每次向后平移自身长度大小的距离，判断是否能够完成平移，也就是平移后的指定位置的子串是否和该前缀相同，若不相同是否是因为当前部分是字符串的一个后缀且该后缀是它的子串。若不满足这个条件，则说明当前前缀无法通过操作成为新的循环节。

若我们成功地将这个前缀平移到了字符串的末尾，使得这个字符串的一个后缀是它的前缀，而去掉这个后缀的部分是它自己复制若干次得到的字符串，则这个前缀可以通过操作成为新的循环节。如果我们按长度从小到大枚举所有前缀，那么选择第一个满足条件的前缀即可。

用字符串哈希进行子串匹配判断单次时间复杂度是 $\Theta(1)$ 的，而这个平移的过程，对于长度为 $i$ 的前缀，最多被平移 $\lceil \frac{n}{i} \rceil$ 次，总次数最多为 $T(\sum_{i=1}^{n}\lceil \frac{n}{i} \rceil)\sim \Theta(n\log n)$ 次，那么时间复杂度为 $\Theta(n\log n)$ 。

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+111;
using ll=long long;
using ull=unsigned long long;
int n,k;
string _s;
const ll xp1=131,xp2=37;
const ll md1=998244353,md2=1e9+9;
ll hs1[N],hs2[N],xps1[N],xps2[N];
pair<ll,ll> ghs(int l,int r)
{
    ll ghs1=(hs1[r]-hs1[l-1]*xps1[r-l+1]%md1+md1)%md1;
    ll ghs2=(hs2[r]-hs2[l-1]*xps2[r-l+1]%md2+md2)%md2;
    return make_pair(ghs1,ghs2);
}
void GHS(string str)
{
    int _n=str.length();xps1[0]=xps2[0]=1ll;
    for(int i=1;i<=_n;++i) xps1[i]=(xps1[i-1]*xp1)%md1,xps2[i]=(xps2[i-1]*xp2)%md2;
    for(int i=1;i<=_n;++i) hs1[i]=(hs1[i-1]*xp1%md1+(str[i-1]-'a'+1))%md1,hs2[i]=(hs2[i-1]*xp2%md2+(str[i-1]-'a'+1))%md2;
}
pair<int,int> getslen()
{
    for(int i=1;i<=n;++i)
    {
        int tp=n-i+1;
        while(tp>=1)
        {
            if((tp-i)<1)
            {
                if(tp==1) return make_pair(i,i);
                else if(tp-1>=1&&ghs(1,tp-1)==ghs(n-tp+2,n)) return make_pair(i,i-tp+1);
                else break;
            }
            if(ghs(n-i+1,n)!=ghs(tp-i,tp-1)) break;
            tp-=i;
        }
    }
    return make_pair(n,n);
}
void clr()
{
    for(int i=1;i<=n;++i) hs1[i]=hs2[i]=0;
}
void solve()
{
    vector<char> ans;
    cin>>_s;GHS(_s);n=_s.length();
    auto xx=getslen();
    for(int i=n-xx.first;i<=n-xx.first+xx.second-1;++i) ans.push_back(_s[i]);
    for(auto x:_s) ans.push_back(x);
    for(auto x:ans) cout<<x;cout<<endl;
    return clr();
}
int main()
{
    int t;cin>>t;
    while(t--) solve();
    return 0;
}

L 不协和音程_终

简要题意：

用可旋转的 $2 \times 2\ \ L$ 型和 $2\times 3 \ \ T$ 型卡片覆盖 $2\times k$ 的网格，要求不重叠无遗漏，设方案数为 $ans_k$ ，给定 $n$ ，求 $\sum_{i=1}^n ans_i \mod 10^9+9$ 。

多测， $T\le 10^6,n\le 10^{18}$ ，强制在线。

题解：

考虑 DP：

设 $f_i$ 为我们恰好填满了前 $i-1$ 列，第 $i$ 列恰有一个空位的方案数，不难发现填满 $2\times k$ 网格的方案数是 $f_{k-1}$ ，考虑放上一个 $2 \times 2\ \ L$ 型卡片即可。

考虑状态转移，比较简单，分别考虑最后加入两种卡片时分别从哪里转移即可，注意如果加入 $2 \times 2\ \ L$ 型卡片需要连着放两个并且第二个有两种放法，转移方程为 $f_{i}=2\times f_{i-3}+f_{i-2}$ 。

同样地，设答案为 $g_i$ ，转移为 $g_{i}=g_{i-1}+f_{i-1}$ 。

很容易想到矩阵加速递推：构造列向量为 $\begin{bmatrix} f_{i}\cr f_{i-1}\cr f_{i-2}\cr g_{i}\end{bmatrix}$ ，则转移矩阵为 $Base=\begin{bmatrix} 0 & 1 & 2 & 0 \cr 1 & 0 & 0 & 0 \cr 0 & 1 & 0 & 0 \cr 1 & 0 & 0 & 1\end{bmatrix}$ ，矩乘的矩阵大小系数 $k=4$ 。

注意到 $n$ 非常大，矩阵快速幂 $\Theta(Tk^3\log n)$ 的时间复杂度根本过不了，需要参照块速幂的思路进行一些优化：

设 $B=10^6$ ，我们预处理三个大小为 $B$ 的矩阵数组：

$mdp_{i}=Base^i,mdp2_i=Base^{B\times i},mdp3_i=Base^{B^2\times i}$ ，可以通过递推以 $\Theta(k^3B)$ 的时间复杂度预处理；

之后，考虑用整除和取余分解 $n=k_1+k_2\times B+k_3 \times B^2$ ，则答案矩阵可表示为 $mdp_{k_1}\times mdp2_{k_2}\times mdp3_{k3}$ ，单次询问时间复杂度 $\Theta(k^3)$ 。

总时间复杂度 $\Theta(Tk^3+Bk^3)$ 。注意 $B$ 可以自行取值，小了会比较麻烦，大了会出事。

然后发现还是会被卡时间空间，（粗口）出题人怎么这么坏啊！

这题递推式还能凹：设 $s_i=\sum_{k=1}^{i}f_{i}$ ，易得 $g_{i}=s_{i-1}$ ，我们把 $\sum_{i=3}^{n}f_i$ 用递推式带入，有：

$(s_n-s_2)=2\times(s_{n-3}-s_{0})+(s_{n-2}-s_{1})$

由初始状态我们可以得到 $s_2=2,s_1=s_0=0$ ，因此我们得到递推式：

$s_{i}=2\times s_{i-3}+s_{i-2}+2$

对这个递推式进行变形：

$(s_{i}+1)=2\times(s_{i-3}+1)+(s_{i-2}+1)$

令 $x_i=s_i+1$ ，有：

$x_i=2\times x_{i-3}+x_{i-2}$

变成了一个齐次三阶递推，构造列向量 $\begin{bmatrix} x_{i}\cr x_{i-1}\cr x_{i-2}\end{bmatrix}$ ，新的转移矩阵为 $A=\begin{bmatrix} 0 & 1 & 2 \cr 1 & 0 & 0 \cr 0 & 1 & 0 \end{bmatrix}$ ，矩乘大小系数被降到了 $k=3$ ！

因此我们求出 $x_{i-1}-1$ 即可。时间复杂度 $\Theta(27(T+B))$ 。

AC代码：

#include<bits/stdc++.h>
using namespace std;
void syncoff()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
}
#define endl '\n'
const int N=1e6+11;
using ll=long long;
const ll mod=1e9+9;
int t,n,k,m,q;
struct martix
{
    ll A[3][3];
    martix(int _init=0)
    {
        if(_init==0) memset(A,0,sizeof(A));
        else if(_init==1)
        for(int i=0;i<=2;++i) for(int j=0;j<=2;++j) A[i][j]=1;
        else if(_init==2)
        {
            memset(A,0,sizeof(A));
            A[0][0]=A[1][1]=A[2][2]=1;
        }
    }
};
martix operator *(const martix &a,const martix &b)
{
    martix ret;
    for(int i=0;i<=2;++i) for(int j=0;j<=2;++j) for(int k=0;k<=2;++k)
    ret.A[i][j]=(ret.A[i][j]+(a.A[i][k]*b.A[k][j]%mod)%mod)%mod;
    return ret;
}
martix base;
ll lastans;
martix mdp[1000005],mdp2[1000005],mdp3[1000005];
const int tlp=1000000;
martix ask(ll _k)
{
    if(_k<=tlp) return mdp[_k];
    else if(_k<=1ll*tlp*tlp)
    {
        int k1=_k/tlp,k2=_k%tlp;
        return mdp[k2]*mdp2[k1];
    }
    ll k1=_k/(1ll*tlp*tlp),k2=_k%(1ll*tlp*tlp);
    return ask(k2)*mdp3[k1];
}
void solve()
{
    ll n;
    cin>>n;n^=lastans;
    if(n<=2) lastans=0,cout<<0<<endl;
    else
    {
        martix ans;
        ans.A[1][0]=1,ans.A[0][0]=3ll,ans.A[2][0]=1;
        ans=ask(n-3)*ans;
        lastans=ans.A[0][0];
        lastans=(lastans-1+mod)%mod;
        cout<<lastans<<endl;
    }
}
int main(int argc,char **argv)
{
    //freopen(argv[1],"r",stdin);
    //freopen(argv[2],"w",stdout);
    syncoff();
    base.A[0][1]=base.A[1][0]=base.A[2][1]=1ll;
    base.A[0][2]=2ll;
    mdp[0]=martix(2);
    for(int i=1;i<=tlp;++i) mdp[i]=base*mdp[i-1];
    mdp2[0]=mdp[0];
    for(int i=1;i<=tlp;++i) mdp2[i]=mdp[tlp]*mdp2[i-1];
    mdp3[0]=mdp[0];
    for(int i=1;i<=tlp;++i) mdp3[i]=mdp2[tlp]*mdp3[i-1];
     t=1;
    cin>>t;
    while(t--) solve();
    return 0;
}

M 照天地苍茫，却有花影成双

题目描述：

赛小息和卡璐璐正在玩一个游戏：

有一堆无尽能源，初始数量为 $n$ 个，两人轮流取无尽能源，赛小息先手，每一次取走的数量必须是一个大于 $0$ 的平方数，最先取完的一方获胜。

如果赛小息获胜，输出 $SXX$ ，如果卡璐璐获胜，输出 $KLL$ ，如果两人平局，输出 $ATD$ 。

解题思路：

首先明确，不可能平局。

如果轮到赛小息时，剩余 $k$ 个无尽能源，假设此时赛小息必败，那么对于 $k$ 加上一个平方数，赛小息必胜。依次递推即可。

注意数据范围，因为每个 $n$ 都会相互关联，所以记忆化一次性处理 $1e5$ 最优。

时间复杂度 $O(N^{\frac{3}{2}} + T)$ 。其中 $N$ 为所有 $n$ 的最大值。

AC代码：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
vector<bool> dp(1e5 + 1, false);

void solve() {
    int n;
    cin >> n;
    cout << (dp[n] ? "SXX\n" : "KLL\n");
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int _ = 1;
    cin >> _;
    for (int i = 1; i <= 1e5; i++) {
        for (int j = 1; j * j <= i; j++) {
            if (!dp[i - j * j]) {
                dp[i] = true;
                break; 
            }
        }
    }
    while (_--) {
        solve();
    }
    return 0;
}