↓跳过正文
韩师ACM集训队

第三届韩山师范学院程序设计竞赛题解

·4112 字·9 分钟

A 宝藏题
#

依题意输出即可。

时间复杂度为\(O(1)\)

#include<bits/stdc++.h>
using namespace std;
int main(){
    cout<<"Hello, Hanshan Normal University!\n";
}

B 2992
#

字符串处理题，对数字输入为字符串。先进行正向输出，输出特定的字符串后，再反向输出即可。

时间复杂度为\(O(|S|)\)，\(|S|\)为字符串长度。

#include<bits/stdc++.h>
using namespace std;
int main(){
    string s;
    cin>>s;
    cout<<s;
    reverse(s.begin(),s.end());
    cout<<", I thought it was "<<s<<".\n";
}

C 可分数列
#

手玩几个样例，可以发现，删除\(a_{4k+1},a_{4t+2}(k,t为非负整数)\)即可满足要求。注意只考虑下标公差为1的情况。

形成的：

$$ a_1, a_2, a_3, a_4, \\ a_5, a_6, a_7, a_8, \\ \dots \\ a_{4(k-1)+1}, a_{4(k-1)+2}, a_{4(k-1)+3}, a_{4(k-1)+4}, \\ a_{4k+2}, a_{4k+3}, a_{4k+4}, a_{4(k+1)+1}, \\ \dots \\ a_{4(t-1)+2}, a_{4(t-1)+3}, a_{4(t-1)+4}, a_{4t+1}, \\ a_{4t+3}, a_{4t+4}, a_{4(t+1)+1}, a_{4(t+1)+2}, \\ \dots \\ a_{4(m-1)+3}, a_{4(m-1)+4}, a_{4m+1}, a_{4m+2}. \\ $$

是可分数列，每行的4个数都组成等差数列。

所以，遍历\(k\)和\(t\)，每一行输出\({4k+1}和{4t+2}\)即可。

时间复杂度为\(O(m^2)\)

#include<bits/stdc++.h>
using namespace std;
int main(){
    int m,n;
    cin>>m;
    n=4*m+2;
    for(int i=1;i<=n;i+=4){
        for(int j=i+1;j<=n;j+=4){
            printf("%d %d\n",i,j);
        }
    }
}

D It’s MyJUMP!!!
#

依题意模拟即可。每跳一步答案加1。

由于\(a_i\)是大于等于\(1\)，所以最大公倍数最小为1，k一般情况下可以到达。

注意\(k\)不可到达的情况:

  • \(k>n\)；
  • 跳的过程中直接跳过了\(k\)。

时间复杂度最大为\(O(n)\)

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e5; 
int a[N];
int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}
signed main(){
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    if(k==1){
        cout<<0<<endl;
        return 0;
    }
    if(k>n){
        cout<<"impossible"<<endl;
        return 0;
    }
    int w=0,flag=0;
    int ans=0;
    for(int i=1;i<=n;i+=w){
        if(i==k) {
            flag=1;
            break;
        }
        else if(i>k) {
            cout<<"impossible"<<endl;
            return 0;
        }
        w=gcd(w,a[i]);
        //cout<<i<<' ';
        ans++;
    }
    if(flag)
        cout<<ans<<endl;
    else
        cout<<"impossible"<<endl;
}

E 折纸小鸟对对碰
#

本题为构造题。题意是构造没有三个字符相连一个字符矩阵，要求进行一次邻项交换后有三个字符相连。

最简单的构造方法，就是构造类似于以下的字符矩阵：奇数行是1212...；偶数行是2121...。只需按照循环变量的奇偶性判断输出即可。

121212
212121
121212

要特殊判断\(n=1\)或\(m=1\)的情况。例如1行4列字符矩阵1121是有解的。这种情况，构造循环输出1121和3343，类似于1121334311213343...排列下去的行矩阵或列矩阵即可。

1和2也可换成其他互不相同的数字，答案不唯一，符合题意即可。

时间复杂度为\(O(nm)\)

#include<iostream>
using namespace std;
int main(){
    int a,b;
    cin>>a>>b;
    if(a==1){
        for(int i=0;i<b;i++){
            if(i%8==0) cout<<'1';
            else if(i%8==1) cout<<'1';
            else if(i%8==2) cout<<'2';
            else if(i%8==3) cout<<'1';
            else if(i%8==4) cout<<'3';
            else if(i%8==5) cout<<'3';
            else if(i%8==6) cout<<'4';
            else if(i%8==7) cout<<'3';
        }
        cout<<'\n';
    }
    else if(b==1){
        for(int i=0;i<a;i++){
            if(i%8==0) cout<<'1';
            else if(i%8==1) cout<<'1';
            else if(i%8==2) cout<<'2';
            else if(i%8==3) cout<<'1';
            else if(i%8==4) cout<<'3';
            else if(i%8==5) cout<<'3';
            else if(i%8==6) cout<<'4';
            else if(i%8==7) cout<<'3';
            cout<<'\n';
        }
    }
    else{
        for(int i=0;i<a;i++){
            for(int j=0;j<b;j++){
                if((i+j)%2) cout<<'1';
                else cout<<'2';
            }
            cout<<'\n';
        }
    }
}

F 摘大果
#

可以进行广度优先搜索或者深度优先搜索。

从起点1开始搜索，搜索到权值大于等于\(k\)的所有的点的最小深度为答案。

注意找不到点的权值大于等于\(k\)的情况,输出-1。

标程使用的是深度优先搜索，需要使用递归，每递归到下一层，记录的树的深度加1，找到符合条件的点时将答案取答案自身和当前深度的最小值。

时间复杂度为\(O(n)\)

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=114519;
vector<int> g[N];
int res=0x3f3f3f3f;
int n,m;
int v[N];
void dfs(int x, int fa,int dep){
    if(v[x]>=m){
        res=min(res,dep);
        return;
    }
    for(auto y:g[x]){
        if(y==fa) continue;
        dfs(y,x,dep+1);
    }
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>v[i];
    }
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(1,-1,0);
    if(res==0x3f3f3f3f)
        cout<<-1<<endl;
    else
        cout<<res<<endl;
    return 0;
}

G 网络时延
#

本题使用Dijkstra算法求解，时间复杂度为\(O(nlogn)\)

可以使用点权化边权的方法然后跑一遍Dijkstra最短路；也可以再跑Dijsktra的过程中加上点权。

注意判断跑出来的结果减去多余的点权。

注意起点和终点可能相同，此时需要特判为\(0\)。

时间复杂度为\(O(nlogn)\)

#include <bits/stdc++.h>
using namespace std;
const double inf = 1e15;
typedef pair<double,int> P;
struct edge{
        int to;
        double cost;
};
int n,a[100005];
vector<edge> G[100005];
double d[100005];

void dij(int s){
        priority_queue<P,vector<P>,greater<P>> que;
        fill(d+1,d+n+1,inf);//注意节点的范围
        d[s]=0;
        que.push(P(0,s));
        while(!que.empty()){
                P p=que.top();que.pop();
                int v=p.second;//当前节点
                if(d[v]<p.first){
                        continue;
                }
                for(int i=0;i<G[v].size();i++){
                        edge e =G[v][i];
                        if(d[e.to]>d[v]+e.cost){//权值更新
                                d[e.to]=d[v]+e.cost;
                                que.push(P(d[e.to],e.to));
                        }
                }
        }
}
int main(){
        int m,s,t;
        cin>>n>>m>>s>>t;
        for(int i=1;i<=n;i++) cin>>a[i];

        for(int i=0;i<m;i++){
                int v,u,w;
                edge ee;
                scanf("%d%d%d",&v,&u,&w);
                double cost= 1.0*w + 0.5*(a[v]+a[u]);
                G[v].push_back({u,cost});
                G[u].push_back({v,cost});
        }
        dij(s);
        
        if(s==t) printf("0\n");
        else if(d[t]==inf) printf("impossible\n");
        else printf("%.0f\n",d[t]-0.5*a[t]-0.5*a[s]);
        return 0;
}

H 康大的比赛
#

我们可以使用二分查找答案和滑动窗口的方法。以下是解决这个问题的思路：

  1. 二分查找：我们可以猜测一个最大难度跨度的值，然后检查是否有可能将题目分配到m场比赛中，使得每场比赛的难度跨度都不超过这个值。

  2. 检查函数：对于一个给定的难度跨度最大值x，我们需要检查是否可以将题目分成不超过m组，且每组的难度跨度都不超过x。这可以通过滑动窗口来实现。

  3. 滑动窗口：我们使用两个指针来表示当前考虑的题目范围的开始和结束位置。我们维护当前窗口内的最大值和最小值，如果这个范围内的难度跨度不超过x，我们就尝试缩小窗口的开始位置，否则扩大窗口的结束位置。

时间复杂度为\(O(nlog(max\{a_i\}))\)

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 200010;

int n,m;
int f[N];

bool check(int mid)
{
	int res = 1;// 分配的比赛场数
	int mind = f[1],maxd = f[1];// 当前窗口内的最小最大值
	for(int i = 2;i <= n;i++)
	{
		if(f[i] - mind > mid || maxd - f[i] > mid) // 如果当前窗口的难度跨度超过了x，移动窗口的开始位置
		{
			res++;// 新增一场比赛
			mind = maxd = f[i];// 重置最大值和最小值
		}
		mind = min(mind,f[i]);
		maxd = max(maxd,f[i]);
		if(res > m) return false;// 检查是否超过m场比赛
	}
	return true;
}

int main()
{
	cin >> n >> m;
	for(int i = 1;i <= n;i++) cin >> f[i];
	
	int l = 0,r = 1e9;
	while(l < r)
	{
		int mid = l + r >> 1;
		if(check(mid)) r = mid;
		else l = mid + 1;
	}
	
	cout << l << '\n';
	return 0;
}

I 欧耶！简简又单单的数学题（Easy Version）
#

本题需要使用宽度优先搜索或者深度优先搜索。

两种操作就相当于dfs（或bfs）的两条路径，暴力搜索到某个数符合误差范围的数就行

\(10^{-5}\)的误差决定了dfs（或bfs）的深度，2的17次方：131072，所以往下搜17层就一定可以找到一个误差范围内的数。

#include<bits/stdc++.h>
using namespace std;
const double m=1e-5;
const int N=1e6;
double a,b,c,d;
int num[N],tem=0,sum=0;
void dfs(double x,int y){
	if(c<x&&x<d)tem=1,num[y]=-1,sum=y;
	if(tem||y>20)return ;
	num[y]=1;
	dfs(x*0.5,y+1);

	if(tem||y>20)return ;
	num[y]=2;
	dfs( (1.0+x)*0.5 , y+1 );

}
int main(){
	cin>>a>>b;
	c=b-m;
	d=b+m;
	dfs(a,0);
	cout<<sum<<"\n";
	for(int i=0;i<sum;i++){
		if(i==sum-1)cout<<num[i];
		else cout<<num[i]<<' ';
	}
}

J 欧耶！简简又单单的数学题（Hard Version）
#

两种操作的本质其实与二进制相关：

操作一（除以2） 实际上就是 二进制位右移动 例： \(0.5_{(0.1)} \div2=0.25_{(0.01)}\)

操作二（除以2再加0.5）实际上就是 先加1再二进制右移，例：\(0.5_{(0.1)} \div2+0.5=0.25_{(0.01)}+0.5_{(0.1)}=0.75_{(0.11)}\)，下标为对应的二进制数。

以0.625举例，0.625的二进制是0.1010000000000，将0.625二进制数的小数位倒序打印就是这题的答案。

2的60次方大概是\(1.1 \times 10^{18}\)，所以60位2进制足以表示所有误差在 \(10^{-18}\)的数。

#include<bits/stdc++.h>
using namespace std;
const int N=1e3;
string a,b;
int c[N],d[N];
void solve(){
    cin >> a >> b;
    memset(c,0,sizeof c);
    for(int i=0;i<b.size();i++){
            if(b[i]=='.')c[i]=0;
                else c[i]=b[i]-'0';
        }
        cout<<"200\n";
        if(c[0]==1){
            for(int i=0;i<200;i++)cout<<"2 ";
            cout<<"\n";
            return ;
        }
        else if(b.size()==1&&c[0]==0){
            for(int i=0;i<200;i++)cout<<"1 ";
            cout<<"\n";
            return ;
        } 
        else {
                for(int i=199;i>=0;i--){
                        for(int j=b.size()-1;j>=0;j--){
                            if(b[j]=='.'){
                                    if(c[j+1]>9){
                                            d[i]=2;
                                            c[j+1]-=10;
                                        }
                                        else d[i]=1;
                                }
                                else {
                                        c[j]=c[j]*2;
                                        if(c[j+1]>9&&j!=b.size()-1){
                                                c[j]++;
                                                c[j+1]-=10;
                                        }
                                }
                        }
                }
                for(int i=0;i<200;i++){
                        cout<<d[i]<<' ';
                }
                cout<<"\n";
        }
}
int main(){
        int T;
        cin>>T;
        while(T--){
                solve();
        }
}

K 另一个游戏
#

本题是一个动态规划问题。

dp的过程就是逆向模拟最优解的过程。

f[i][j]=起点为i，长度为j时，先手分数-后手分数的最大值。（请注意这里的长度=终点-起点，也就意味着终点在i+j）

那么就有2种情况：

从左边取，\(f[i][j]=a[i]-f[i+1][j-1]\)

从右边取，\(f[i][j]=a[i+j]-f[i][j-1]\)

#include <iostream>
#include <fstream>

using namespace std;

int dp[510][510];
int n;
int num[510];
int sum;

int main() {
        cin >> n;
        for(int i = 1; i < n + 1; i++)cin >> num[i];
        for(int i = 1; i < n + 1; i++) {
                //初始化
                dp[i][i] = num[i];
                sum += num[i];
        }
        for(int i = 2; i < n + 1; i++) //手动模拟第二层dp矩阵 
                dp[i-1][i] = max(dp[i][i], dp[i-1][i-1]);
        for(int i = n - 2; i > 0; i--) {//i要倒着跑 
                for(int j = i; j < n + 1; j++) { //j要正着跑 
                        dp[i][j] = max(num[i] + min(dp[i+1][j-1], dp[i+2][j]), num[j] + min(dp[i][j-2], dp[i+1][j-1]));
                        //转移方程 
                }
        }
        cout << dp[1][n] << ' ' << sum - dp[1][n] << endl;
        return 0;
}

我们发现，如果我们采用这样的状态定义，每次只会用到上一级的结果，于是我们就可以进行两行的滚动数组优化。

#include<bits/stdc++.h>
using namespace std;
int n,dp[505][2],a[505],tot=0;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        dp[i][0]=a[i];
        tot+=a[i];//tot记录和
    }
    for(int i=1;i<n;i++)//长度枚举
    {
        for(int j=1;j+i<=n;j++)//起点枚举
        {
            dp[j][i&1]=max(a[j+i]-dp[j][1-(i&1)],a[j]-dp[j+1][1-(i&1)]);
        }
    }
    printf("%d %d",(tot+dp[1][1-(n&1)])>>1,(tot-dp[1][1-n&1])>>1);
    return 0;
}

L 长板效应
#

本题使用线段树维护区间最大值进行求解。

对于每次修改操作，我们使用懒标记来记录当前区间是否被修改过。在区间查询过程中，向下传递标记，更新区间

对于每次查询，我们先查询区间\([l,r]\)的最大值，记为\(tmp\)。这道题的必要的思路是寻找\([l,r]\)左右两边的值大于\(tmp\)的最近端点。

因此我们二分区间的最大值去查找这两个端点，先以\(l\)为左端点，以\(n\)为右端点，二分查找最左端点\(f\), 使得区间\([l,f]\)的最大值恰好大于 \(tmp\)。 然后，以\(1\)为左端点，以\(r\)为右端点，二分查找最右端点\(g\), 使得区间\([g,r]\)的最大值恰好大于\(tmp\)。

答案要求的区间包含\([l,r]\)，而且包含\(f\)或\(g\)的，运用容斥原理解得，答案是\(f\times(n-r+1) + (n-g+1)\times l - f\times(n-g+1)\)

时间复杂度为\(O(nlogn + qlognlogn)\)

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
#define LD (o<<1)
#define RD (o<<1|1)
#define INF 0x7fffffff
#define int long long
struct Node{
        int l,r;
        int maxv,add;
};
struct Tree{
        Node t[N<<2];
        int a[N];
        inline void pushup(Node &o,Node &ld,Node &rd){
                o.maxv=max(ld.maxv,rd.maxv);
        }
        inline void pushdown(Node &o,Node &ld,Node &rd){
        ld.add+=o.add;ld.maxv+=o.add;
        rd.add+=o.add;rd.maxv+=o.add;
        o.add=0;
        }
        void build(int o,int l,int r){
                t[o].l=l;t[o].r=r;t[o].add=0;
                if(l==r){t[o].maxv=a[l];return;}
                int mid=(l+r)>>1;
                build(LD,l,mid);
                build(RD,mid+1,r);
                pushup(t[o],t[LD],t[RD]);
        }
        void update(int o,int l,int r,int v){
                if(l<=t[o].l&&t[o].r<=r){t[o].add+=v;t[o].maxv+=v;return;}
                pushdown(t[o],t[LD],t[RD]);
                int mid=(t[o].l+t[o].r)>>1;
                if(mid>=l)update(LD,l,r,v);
                if(mid<r)update(RD,l,r,v);
                pushup(t[o],t[LD],t[RD]);
        }
        int query(int o,int l,int r){
                if(l<=t[o].l&&t[o].r<=r)return t[o].maxv;
                pushdown(t[o],t[LD],t[RD]);
                int ans=0,mid=(t[o].l+t[o].r)>>1;
                if(mid>=l)ans=max(ans,query(LD,l,r));
                if(mid<r)ans=max(ans,query(RD,l,r));
                pushup(t[o],t[LD],t[RD]);
                return ans;
        }
}A;
int n,m;
signed main(){
        scanf("%lld%lld",&n,&m);
        for(int i=1;i<=n;i++)scanf("%lld",&A.a[i]);
        A.build(1,1,n);
        for(int i=1;i<=m;i++){
            int l,r;
            string t;
            cin>>t>>l>>r;
            if(t=="A"){
                int v;
                cin>>v;
                A.update(1,l,r,v);
            }
            if(t=="Q"){
                int lb=1,rb=r,ans1,ans2;
                int tmp=A.query(1,l,r);
                while(lb<rb){
                    int mid =lb+rb>>1;
                    if(A.query(1,mid,rb)<=tmp) rb=mid;
                    else lb=mid+1;
                }
                ans1=lb;
                lb=l,rb=n;
                while(lb<rb){
                    int mid =lb+rb+1>>1;
                    if(A.query(1,lb,mid)<=tmp) lb=mid;
                    else rb=mid-1;
                }
                ans2=lb;
                int ans = (ans1-1)*(n-r+1) + (n-ans2)*l - (ans1-1)*(n-ans2);
                printf("%lld\n",ans);
            }
        }
        return 0;
}

M 点亮“121周年生日”
#

原式先化为：

$$ F(n)=\sum_{i=1}^{n} \sum_{j=1}^n C_{max(i ,j)}^{min(i, j)} 121^{ij} $$

$$ =2 \sum_{i=1}^n \sum_{j=1}^i C_{i}^{j} 121^{ij}-\sum_{i=1}^n 121^{i^2} $$

$$ =2 \sum_{i=1}^n \sum_{j=1}^i \frac{i!}{j!(i-j)!} 11^{2ij}-\sum_{i=1}^n 121^{i^2} $$

$$ =2 \sum_{i=1}^n i! \sum_{j=1}^i \frac{1}{j!(i-j)!} 11^{i^2+j^2-(i-j)^2}-\sum_{i=1}^n 121^{i^2} $$

$$ = \textcolor{orange}{2 \sum_{i=1}^n i! 11^{i^2} \sum_{j=1}^i \frac{11^{j^2}}{j!} \frac{11^{-(i-j)^2}}{(i-j)!}}-\sum_{i=1}^n 121^{i^2} $$

令

$$ f(x) = \frac{11^{x^2}}{x!}, g(x)=\frac{11^{-x^2}}{x!} $$

显然，

$$ \sum_{j=1}^i \frac{11^{j^2}}{j!} \frac{11^{-(i-j)^2}}{(i-j)!}=\sum_{j=1}^i f(i) g(i-j) $$

是一个卷积，可以使用 FFT 来加速多项式乘法计算。由于题目要求对答案进行取模，因此使用NTT（快速数论变换）。然后把第\(i\)项的系数乘\(i! 11^{i^2}\)，并求和并乘\(2\)即可得到左边和式(橙色部分)答案。

对于右边的\(\sum_{i=1}^n 121^{i^2}\)，可以进行暴力求和，得到右边和式的答案。左边式子和右边式子相减即可得到最终答案。

对于多个测试组数，我们可以进行预处理，在求和的时候把每一个答案存在数组里，然后每次询问的时候直接取数组里的值即可。

时间复杂度为\(O(nlogn)\)，主要用在NTT计算上。

#include <vector>
#include <iostream>
#define int long long
#define poly vector<int>

using namespace std;
const int Maxn=5e5+7;
const int M=1e5+1;
const int mod=998244353;
int ksm(int a,int b,int mod){
    int z=1;
    while(b){
        if(b&1) z=1ll*z*a%mod;
        a=1ll*a*a%mod;
        b>>=1;
    }
    return z;
}
int inv(int x){
    return ksm(x,mod-2,mod);
}

namespace Poly{
    const int mod=998244353,g=3,invg=332748118;
    int lim,len,rev[Maxn],invlim;
    inline void init(int l1,int l2){
        lim=1,len=0;
        while(lim<=l1+l2) lim<<=1,len++;
        for(int i=0;i<lim;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(len-1));
        invlim=ksm(lim,mod-2,mod);
    }
    inline void NTT(poly &f,int type){
        for(int i=0;i<lim;i++) if(i<rev[i]) swap(f[i],f[rev[i]]);
        for(int m=2;m<=lim;m<<=1){
            int wn=ksm(type?g:invg,(mod-1)/m,mod);
            for(int i=0;i<lim;i+=m){
                int w=1;
                for(int j=0;j<m/2;j++){
                    int u=f[i+j],v=1ll*w*f[i+j+m/2]%mod;
                    f[i+j]=(u+v)%mod,f[i+j+m/2]=(u-v+mod)%mod;
                    w=1ll*wn*w%mod;
                }
            }
        }
        if(!type){
            for(int i=0;i<lim;i++) f[i]=1ll*f[i]*invlim%mod;
        }
    }   
    inline poly mul(poly f,poly g){
        int lf=f.size(),lg=g.size();
        init(lf,lg);
        f.resize(lim),g.resize(lim);
        poly h(lim);
        NTT(f,1);NTT(g,1);
        for(int i=0;i<lim;i++) h[i]=1ll*f[i]*g[i]%mod;
        NTT(h,0);
        return h; 
    }
}
int Fact[Maxn],INV[Maxn];
void init( int n ) {
    Fact[ 0 ] = 1;
    for( int i = 1; i <= n; ++i ) Fact[ i ] = Fact[ i - 1 ] * i % mod;
    INV[ n ] = inv( Fact[ n ]);
    for( int i = n - 1; i >= 0; --i ) INV[ i ] = INV[ i + 1 ] * ( i + 1 ) % mod;
    return;
}
int ans[Maxn], con[Maxn];
signed main(){
    init(M+1);
    poly f(M+1),g(M+1);

    for(int i=0;i<=M;i++){
        f[i]=ksm(11,i*i,mod)*INV[i]%mod;
        g[i]=ksm(11,(-i * i) % (mod - 1) + mod - 1,mod)*INV[i]%mod;
    }
    f[0]=0;
    poly h=Poly::mul(f,g);
    for(int i=1;i<=M;i++){
        ans[i]=(ans[i-1]+Fact[i]*ksm(11,i*i,mod)%mod*h[i]%mod)%mod;
    }
    for(int i=1;i<=M;i++){
        ans[i]=(ans[i]*2)%mod;
    }
    for(int i=1;i<=M;i++){
        con[i]=(con[i-1]+ksm(121,i*i,mod)%mod)%mod;
    }
    int t;
    cin>>t;
    while(t--){
        int q;
        cin >> q;
        cout<<(ans[q]-con[q]+mod)%mod<<'\n';
    }
    
    return 0;
}