如果这篇博客帮助到你，可以请我喝一杯咖啡~
CC BY 4.0 （除特别声明或转载文章外）
Magic Mirror
#include <cstdio>
#include <cstring>
int T;
char s[20],a[20]="JESSIE",b[20]="jessie";
bool o;
int main()
{
scanf("%d",&T);
while (T--)
{
scanf("%s",s);
if (strlen(s)!=6)
{
printf("Dare you say that again?\n");
continue;
}
o=true;
for (int i=0;i<6;i++)
if ((s[i]!=a[i])&&(s[i]!=b[i]))
{
o=false;
break;
}
if (o) printf("Good guy!\n");
else printf("Dare you say that again?\n");
}
return 0;
}
Mathematical Curse
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int t,n,m,k;
long long a[1010];
char s[10];
long long mx[1010][10],mn[1010][10];
int main()
{
scanf("%d",&t);
while (t--)
{
scanf("%d%d%d",&n,&m,&k);
for (int i=1;i<=n;i++) scanf("%lld",&a[i]);
scanf("%s",s);
memset(mx,0,sizeof(mx));
memset(mn,0,sizeof(mn));
mx[0][0]=mn[0][0]=k;
for (int i=1;i<=n;i++)
for (int j=1;(j<=m)&&(j<=i);j++)
{
mx[i][0]=mn[i][0]=k;
if (s[j-1]=='+') mx[i][j]=mx[i-1][j-1]+a[i],mn[i][j]=mn[i-1][j-1]+a[i];
else if (s[j-1]=='-') mx[i][j]=mx[i-1][j-1]-a[i],mn[i][j]=mn[i-1][j-1]-a[i];
else if (s[j-1]=='*')
{
if (a[i]>=0) mx[i][j]=mx[i-1][j-1]*a[i],mn[i][j]=mn[i-1][j-1]*a[i];
else mx[i][j]=mn[i-1][j-1]*a[i],mn[i][j]=mx[i-1][j-1]*a[i];
}
else
{
if (a[i]>=0) mx[i][j]=mx[i-1][j-1]/a[i],mn[i][j]=mn[i-1][j-1]/a[i];
else mx[i][j]=mn[i-1][j-1]/a[i],mn[i][j]=mx[i-1][j-1]/a[i];
}
if (i>j) mx[i][j]=max(mx[i][j],mx[i-1][j]),mn[i][j]=min(mn[i][j],mn[i-1][j]);
}
printf("%lld\n",mx[n][m]);
}
return 0;
}
Password
Sequence
Jiu Yuan Wants to Eat
链剖+双标记维护区间和，区间取反操作等价于区间乘 -1 后区间加 -1 。 时限卡的有点紧，线段树用 vector 建的时候卡时限 2832ms/3000ms，改成数组也要跑 2448ms/3000ms。
#include<cstdio>
#include<vector>
using namespace std;
typedef unsigned long long ll;
struct SegmentTree
{
struct Node
{
int l,r;
ll mul,add,sum;
void set(ll m,ll a)
{
mul*=m,add=add*m+a,sum=sum*m+a*(r-l+1);
}
void up(const Node &lc,const Node &rc)
{
sum=lc.sum+rc.sum;
}
void down(Node &lc,Node &rc)
{
lc.set(mul,add),rc.set(mul,add),mul=1,add=0;
}
};
vector<Node> v;
SegmentTree(int N):v(N<<2)
{
build(1,N);
}
void build(int l,int r,int rt=1)
{
v[rt]= {l,r};
if(l>=r)return;
int m=l+r>>1;
build(l,m,rt<<1),build(m+1,r,rt<<1|1),v[rt].up(v[rt<<1],v[rt<<1|1]);
}
void set(int l,int r,ll mul,ll add,int rt=1)
{
if(l<=v[rt].l&&v[rt].r<=r)return v[rt].set(mul,add);
v[rt].down(v[rt<<1],v[rt<<1|1]);
int m=v[rt].l+v[rt].r>>1;
if(m>=r)set(l,r,mul,add,rt<<1);
else if(m<l)set(l,r,mul,add,rt<<1|1);
else set(l,m,mul,add,rt<<1),set(m+1,r,mul,add,rt<<1|1);
v[rt].up(v[rt<<1],v[rt<<1|1]);
}
Node ask(int l,int r,int rt=1)
{
if(l<=v[rt].l&&v[rt].r<=r)return v[rt];
v[rt].down(v[rt<<1],v[rt<<1|1]);
int m=v[rt].l+v[rt].r>>1;
if(m>=r)return ask(l,r,rt<<1);
if(m<l)return ask(l,r,rt<<1|1);
return v[0].up(ask(l,m,rt<<1),ask(m+1,r,rt<<1|1)),v[0];
}
};
struct Graph
{
struct Vertex
{
vector<int> o,i;//相关出边和入边编号
int siz,dep,top,dfn;//树链剖分中使用，依次代表子树节点数、深度、所在链的顶端节点、dfs序
};
typedef pair<int,int> Edge;
vector<Vertex> v;//点集
vector<Edge> e;//边集
Graph(int n):v(n) {}
void add(const Edge &ed)
{
v[ed.first].o.push_back(e.size());
v[ed.second].i.push_back(e.size());
e.push_back(ed);
}
int ch(int u,int i=0)//u的第i个孩子节点
{
return e[v[u].o[i]].second;
}
int fa(int u,int i=0)//u的第i个父节点
{
return e[v[u].i[i]].first;
}
};
struct Diagram:Graph
{
SegmentTree data;
Diagram(const Graph &g,int root):
Graph(g.v.size()),data(g.v.size())
{
int cnt=v[root].dfn=v[root].dep=1;
build(root,g),dfs(v[root].top=root,cnt);
}
void build(int u,const Graph &g)//无向图dfs建树，且重边在最前，u为根节点
{
v[u].siz=1;
for(int i=0,k,to; i<g.v[u].o.size(); ++i)
if(k=g.v[u].o[i],to=g.e[k].second,!v[to].siz)//没访问过的点siz默认0
{
build(to,g),v[u].siz+=v[to].siz,add(g.e[k]);
if(v[ch(u)].siz<v[to].siz)//重边移到最前
swap(v[u].o.front(),v[u].o.back());
}
}
void dfs(int u,int &cnt)
{
for(int i=0,to; i<v[u].o.size(); ++i)
{
v[to=ch(u,i)].dep=v[u].dep+1;
v[to].top=i?to:v[u].top;
v[to].dfn=++cnt;
dfs(to,cnt);
}
}
void set(int x,int y,ll mul,ll add)
{
for(; v[x].top!=v[y].top; x=fa(v[x].top))
{
if(v[v[x].top].dep<v[v[y].top].dep)swap(x,y);
data.set(v[v[x].top].dfn,v[x].dfn,mul,add);
}
if(v[x].dep<v[y].dep)swap(x,y);
data.set(v[y].dfn,v[x].dfn,mul,add);
}
SegmentTree::Node ask(int x,int y)
{
SegmentTree::Node ans;
for(ans.sum=0; v[x].top!=v[y].top; x=fa(v[x].top))
{
if(v[v[x].top].dep<v[v[y].top].dep)swap(x,y);
ans.up(ans,data.ask(v[v[x].top].dfn,v[x].dfn));
}
if(v[x].dep<v[y].dep)swap(x,y);
return ans.up(ans,data.ask(v[y].dfn,v[x].dfn)),ans;
}
};
int main()
{
for(int n; ~scanf("%d",&n);)
{
Graph g(n+1);
for(int i=2,b; i<=n; ++i)
scanf("%d",&b),g.add({b,i});
Diagram d(g,1);
scanf("%d",&n);
for(int i=0,u,v; i<n; ++i)
{
ll x;
scanf("%llu%d%d",&x,&u,&v);
if(x==1)scanf("%llu",&x),d.set(u,v,x,0);
else if(x==2)scanf("%llu",&x),d.set(u,v,1,x);
else if(x==3)d.set(u,v,-1,-1);
else printf("%llu\n",d.ask(u,v).sum);
}
}
}
Modular Production Line
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll N=100009,NPOS=-1,INF=1e18;
struct Ranker:vector<ll>
{
void init()
{
sort(begin(),end()),resize(unique(begin(),end())-begin());
}
int ask(ll x)const
{
return lower_bound(begin(),end(),x)-begin();
}
};
struct Graph
{
struct Vertex
{
vector<int> a/*,b*/;//相关出边和入边编号
//int siz,dep,top,dfn;//树链剖分中使用，依次代表子树节点数、深度、所在链的顶端节点、dfs序
};
struct Edge
{
int from,to;
ll dist,cap;//边长、容量，图论算法使用
};
vector<Vertex> v;//点集
vector<Edge> e;//边集
Graph(int n):v(n) {}
void add(const Edge &ed)
{
if(ed.from==ed.to)return;//如果有需要请拆点
v[ed.from].a.push_back(e.size());
//v[ed.to].b.push_back(e.size());
e.push_back(ed);
}
};
struct EdmondKarp:Graph
{
ll flow,cost;
vector<ll> f;
EdmondKarp(int n):Graph(n) {}
void add(Edge ed)
{
Graph::add(ed);
swap(ed.from,ed.to),ed.cap=0,ed.dist*=-1;
Graph::add(ed);
}
void ask(int s,int t)
{
vector<int> p(v.size(),NPOS);
for(f.assign(e.size(),flow=cost=0);;)
{
vector<ll> d(v.size(),INF);
vector<int> flag(v.size(),d[s]=0);
for(deque<int> q(flag[s]=1,s); !q.empty(); q.pop_front())
for(int u=q.front(),i=flag[u]=0,k,to; i<v[u].a.size(); ++i)
if(k=v[u].a[i],to=e[k].to,
e[k].cap>f[k]&&d[to]>d[u]+e[k].dist)
{
d[to]=d[u]+e[k].dist,p[to]=k;
if(!flag[to])q.push_back(to),flag[to]=1;
}
if(d[t]==INF)return;
ll _f=INF;
for(int u=t; u!=s; u=e[p[u]].from)
_f=min(_f,e[p[u]].cap-f[p[u]]);
for(int u=t; u!=s; u=e[p[u]].from)
cost+=_f*e[p[u]].dist,f[p[u]]+=_f,f[p[u]^1]-=_f;
flow+=_f;
}
}
};
int t,n,m,k,x[N],y[N],w[N];
int main()
{
for(scanf("%d",&t); t--;)
{
Ranker rk;
scanf("%d%d%d",&n,&k,&m);
for(int i=0; i<m; ++i)
{
scanf("%d%d%d",&x[i],&y[i],&w[i]);
rk.push_back(x[i]);
rk.push_back(++y[i]);
}
rk.init();
EdmondKarp g(rk.size()+2);
for(int i=0; i<rk.size(); ++i)g.add({i,i+1,0,k});
for(int i=0; i<m; ++i)g.add({rk.ask(x[i]),rk.ask(y[i]),-w[i],1});
g.add({rk.size()+1,0,0,k});
g.ask(rk.size()+1,rk.size());
printf("%lld\n",-g.cost);
}
}
Give Candies
答案是$2^{n-2}$，用费马小定理把指数对 M-1 取模后进行运算避免更多的高精度运算。
#include<stdio.h>
#define mul(a,b,c) (1LL*(a)*(b)%(c))
typedef int ll;
const ll M=1e9+7;
ll pow(ll a,ll b,ll m)
{
ll r=1;
for(a%=m; b; b>>=1,a=mul(a,a,m))
if(b&1)r=mul(r,a,m);
return r;
}
char s[100009];
int t,n;
int main()
{
for(scanf("%d",&t); t--;)
{
scanf("%s",s);
for(int i=n=0; s[i]; ++i)
n=mul(n,10,M-1)+s[i]-'0';
printf("%d\n",pow(2,n+M-2,M));
}
}
String and Times
拉一个后缀数组的板子跑掉了。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
typedef long long ll;
struct SufArr
{
vector<int> sa,rk,h;
SufArr(const vector<int> &s,int m):sa(s.size(),0),rk(s),h(s.size(),0)
{
vector<int> cnt(s.size()+m,0);
for(int i=0; i<s.size(); ++i)++cnt[rk[i]];
for(int i=1; i<m; ++i)cnt[i]+=cnt[i-1];
for(int i=0; i<s.size(); ++i)sa[--cnt[rk[i]]]=i;
for(int k=1,j=0; k<=s.size()&&j<s.size()-1; k<<=1)
{
for(int i=0; i<s.size(); ++i)
{
if(j=sa[i]-k,j<0)j+=s.size();
h[cnt[rk[j]]++]=j;
}
cnt[0]=sa[h[0]]=j=0;
for(int i=1; i<s.size(); ++i)
{
if(rk[h[i]]!=rk[h[i-1]]||rk[h[i]+k]!=rk[h[i-1]+k])
cnt[++j]=i;
sa[h[i]]=j;
}
swap(rk,sa),swap(sa,h);
}
for(int i=0,k=0,j=rk[0]; i<s.size()-1; ++i,++k)
for(; ~k&&s[i]!=s[sa[j-1]+k]; j=rk[sa[j]+1],--k)
h[j]=k;
}
};
struct SparseTable
{
typedef int ll;
vector<vector<ll> > f;
SparseTable(const vector<ll> &a):f(log2(a.size())+1,a)
{
for(int k=0; k+1<f.size(); ++k)
for(int i=0; i+(1<<k)<a.size(); ++i)
f[k+1][i]=min(f[k][i],f[k][i+(1<<k)]);
}
ll ask(int l,int r)
{
int k=log2(r-l+1);
return min(f[k][l],f[k][r+1-(1<<k)]);
}
};
ll cal(SufArr &sa,SparseTable &st,int k)//原串中至少出现k次的子串数量
{
ll ans=0;
if(k>1)
for(int l=2,r=k; r<sa.h.size(); ++l,++r)
ans+=max(st.ask(l,r)-sa.h[l-1],0);
else
for(int i=1; i<sa.h.size(); ++i)
ans+=sa.h.size()-1-sa.sa[i]-sa.h[i];
return ans;
}
char s[2000009];
int main()
{
for(int a,b; ~scanf("%s%d%d",s,&a,&b);)
{
SufArr sa(vector<int>(s,s+strlen(s)+1),'Z'+1);
SparseTable st(sa.h);
printf("%lld\n",cal(sa,st,a)-cal(sa,st,b+1));
}
}
Save the Room
#include<stdio.h>
int main()
{
for(int a,b,c; ~scanf("%d%d%d",&a,&b,&c);)
printf(a%2&&b%2&&c%2?"No\n":"Yes\n");
}
Participate in E-sports
交了个高精度开根号上去。
#include<cmath>
#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;
struct Wint:vector<int>//继承vector
{
static const int width=9,base=1e9;
Wint(unsigned long long n=0)//普通初始化，当整型数和Wint同时运算时会提升至Wint
{
for(; n; n/=base)push_back(n%base);
}
explicit Wint(const string &s)//字符串初始化函数，未判断字符串合法情况
{
for(int len=int(s.size()-1)/width+1,b,e,i=0; i<len; ++i)
for(e=s.size()-i*width,b=max(0,e-width),push_back(0); b!=e; ++b)
back()=back()*10+s[b]-'0';
trim(0);
}
Wint& trim(bool up=1)//去前导0，是否需要进位，很常用的小函数，为方便返回自身
{
for(int i=1; up&&i<size(); ++i)
{
if((*this)[i-1]<0)--(*this)[i],(*this)[i-1]+=base;
if((*this)[i-1]>=base)(*this)[i]+=(*this)[i-1]/base,(*this)[i-1]%=base;
}
while(!empty()&&back()<=0)pop_back();
for(; up&&!empty()&&back()>=base; (*this)[size()-2]%=base)
push_back(back()/base);
return *this;
}
friend istream& operator>>(istream &is,Wint &n)
{
string s;//懒
return is>>s,n=Wint(s),is;
}
friend ostream& operator<<(ostream &os,const Wint &n)
{
if(n.empty())return os.put('0');
os<<n.back();
char ch=os.fill('0');
for(int i=n.size()-2; ~i; --i)
os.width(n.width),os<<n[i];
return os.fill(ch),os;
}
friend bool operator<(const Wint &a,const Wint &b)
{
if(a.size()!=b.size())return a.size()<b.size();
for(int i=a.size()-1; ~i; --i)
if(a[i]!=b[i])return a[i]<b[i];
return 0;
}
friend bool operator>(const Wint &a,const Wint &b)
{
return b<a;
}
friend bool operator<=(const Wint &a,const Wint &b)
{
return !(a>b);
}
friend bool operator>=(const Wint &a,const Wint &b)
{
return !(a<b);
}
Wint& operator+=(const Wint &b)
{
if(size()<b.size())resize(b.size());//保证有足够的位数
for(int i=0; i<b.size(); ++i)(*this)[i]+=b[i];
return trim();//单独进位防自运算
}
friend Wint operator+(Wint a,const Wint &b)
{
return a+=b;
}
Wint& operator++()//前置版本
{
return *this+=1;//懒
}
Wint operator++(int)//后置版本
{
Wint b(*this);
return ++*this,b;
}
Wint& operator-=(const Wint &b)//a<b会使a变为0
{
if(size()<b.size())resize(b.size());//保证有足够的位数
for(int i=0; i<b.size(); ++i)(*this)[i]-=b[i];
return trim();//单独进位防自运算
}
friend Wint operator-(Wint a,const Wint &b)
{
return a-=b;
}
Wint& operator--()//前置版本
{
return *this-=1;//懒
}
Wint operator--(int)//后置版本
{
Wint b(*this);
return --*this,b;
}
Wint& operator*=(const Wint &b)//高精度乘法，常规写法
{
Wint c;
c.assign(size()+b.size(),0);
for(int j=0,k,l; j<b.size(); ++j)
if(b[j])//稀疏优化，特殊情况很有效
for(int i=0; i<size(); ++i)
{
unsigned long long n=(*this)[i];
for(n*=b[j],k=i+j; n; n/=base)
c[k++]+=n%base;
for(l=i+j; c[l]>=base||l+1<k; c[l++]%=base)
c[l+1]+=c[l]/base;
}
return swap(c),trim(0);
}
/*
Wint& operator*=(const Wint &b)//一种效率略高但对位宽有限制的写法
{
vector<unsigned long long> n(size()+b.size(),0);//防爆int
//乘法算完后统一进位效率高，防止乘法溢出（unsigned long long范围0~1.8e19）
//位宽为9时size()不能超过18（十进制162位），位宽为8时size()不能超过1800（十进制14400位）等等。
for(int j=0; j!=b.size(); ++j)
if(b[j])//稀疏优化，特殊情况很有效
for(int i=0; i!=size(); ++i)
n[i+j]+=(unsigned long long)(*this)[i]*b[j];
for(int i=1; i<n.size(); ++i)//这里用<防止位数0，单独进位防自运算
n[i]+=n[i-1]/base,n[i-1]%=base;
return assign(n.begin(),n.end()),trim(0);
}
Wint& operator*=(const Wint &b)//fft优化乘法，注意double仅15位有效数字，调小Wint::width不超过2，计算自2*log2(base)+2*log2(len)<53
{
vector<ll> ax(begin(),end()),bx(b.begin(),b.end());
ax=FFT(size()+b.size()).ask(ax,bx);
for(int i=1; i<ax.size(); ++i)
ax[i]+=ax[i-1]/base,ax[i-1]%=base;
return assign(ax.begin(),ax.end()),trim(0);
}
Wint& operator*=(const Wint &b)//ntt优化，Wint::width不超过2
{
vector<ll> ax(begin(),end()),bx(b.begin(),b.end());
ax=FNTT(size()+b.size(),(7<<26)+1,3).ask(ax,bx);
for(int i=1; i<ax.size(); ++i)
ax[i]+=ax[i-1]/base,ax[i-1]%=base;
return assign(ax.begin(),ax.end()),trim(0);
}
*/
friend Wint operator*(Wint a,const Wint &b)
{
return a*=b;
}
Wint& operator/=(Wint b)
{
Wint r,c,d=b.base/(b.back()+1);
*this*=d,b*=d,c.assign(size(),0);
for(int i=size()-1; ~i; --i)
{
r.insert(r.begin(),(*this)[i]);
unsigned long long s=0;
for(int j=b.size(); j+1>=b.size(); --j)//b.size()==0肯定第一行就出问题的
s=s*b.base+(j<r.size()?r[j]:0);
for(d=c[i]=s/b.back(),d*=b; r<d; r+=b)--c[i];
r-=d;
}
return swap(c),trim(0);//r为加倍后的余数，可通过高精度除低精度得到真正余数，此处略
}
friend Wint operator/(Wint a,const Wint &b)
{
return a/=b;
}
Wint& operator%=(const Wint &b)
{
return *this-=*this/b*b;
}
friend Wint operator%(Wint a,const Wint &b)
{
return a%=b;
}
//开平方，改自ZJU模板
bool cmp(long long c,int d,const Wint &b)const
{
if((int)b.size()-(int)size()<d+1&&c)return 1;
long long t=0;
for(int i=b.size()-1,lo=-(base<<1); lo<=t&&t<=0&&~i; --i)
if(t=t*base-b[i],0<=i-d-1&&i-d-1<size())
t+=(*this)[i-d-1]*c;
return t>0;
}
Wint& sub(const Wint &b,long long k,int d)
{
int l=b.size()+d;
for(int i=d+1; i<=l; ++i)
{
long long tmp=(*this)[i]-k*b[i-d-1];
if(tmp<0)
{
(*this)[i+1]+=(tmp-base+1)/base;
(*this)[i]=tmp-(tmp-base+1)/base*base;
}
else (*this)[i]=tmp;
}
for(int i=l+1; i<size()&&(*this)[i]<0; ++i)
{
(*this)[i+1]+=((*this)[i]-base+1)/base;
(*this)[i]-=((*this)[i]-base+1)/base*base;
}
return trim(0);
}
friend Wint sqrt(Wint a)
{
Wint n;
n.assign(a.size()+1>>1,0);
for(int i=n.size()-1,l,r; ~i; --i)
{
for(l=0,r=a.base,n[i]=l+r>>1; r-l>1; n[i]=l+r>>1)
{
if(n.cmp(n[i],i-1,a))r=n[i];
else l=n[i];
}
a.sub(n,n[i],i-1),n[i]+=l+r>>1;
}
for(int i=0; i<n.size(); ++i)n[i]>>=1;
return n.trim(0);
}
/*
friend Wint sqrt(const Wint &a)//常规牛顿迭代实现的开平方算法，慢但是好敲
{
Wint b=a,c=(b+1)/2;
while(b!=c)swap(b,c),c=(b+a/b)/2;
return c;
}
friend Wint sqrt(const Wint &a)
{
Wint ret,t;
ret.assign((a.size()+1)>>1,0);
for(int i=ret.size()-1,l,r; ~i; --i)
{
for(l=0,r=a.base; r-l>1;)
{
ret[i]=l+(r-l)/2;
t=ret*ret;
if(a<t)r=ret[i];
else l=ret[i];
}
if(!l&&i==ret.size()-1)ret.pop_back();
else ret[i]=l;
}
return ret;
}
*/
};
int check(Wint n)
{
Wint sn=sqrt(n);
return sn*sn==n;
}
int main()
{
int t;
for(cin>>t; t--;)
{
Wint n;
cin>>n;
int ans=check(n)*2+check(n*(n-1)/2);
cout<<(ans==0?"League of Legends\n":
ans==1?"Clash Royale\n":
ans==2?"Hearth Stone\n":
"Arena of Valor\n");
}
}
Transport Ship
拆成 01 背包。
#include<stdio.h>
#include<string.h>
const int N=511,S=32767>>1,M=1e9+7;
int t,n,q,m,v[N],f[N][S];
int main()
{
for(scanf("%d",&t); t--;)
{
scanf("%d%d",&n,&q);
for(int i=m=0,V,C; i<n; ++i)
{
scanf("%d%d",&V,&C);
for(int i=0; i<C; ++i)
v[++m]=(1<<i)*V;
}
for(int i=f[0][0]=1; i<=m; ++i)
for(int s=0; s<S; ++s)
if(f[i][s]=f[i-1][s],s>=v[i])
f[i][s]=(f[i][s]+f[i-1][s-v[i]])%M;
for(int i=0,s; i<q; ++i)
{
scanf("%d",&s);
printf("%d\n",f[m][s]);
}
}
}
Poor God Water
矩阵乘一下。
#include<cstdio>
#include<algorithm>
#define mul(a,b,c) (1LL*(a)*(b)%(c))
using namespace std;
typedef long long ll;
const ll N=9,M=1e9+7;
struct Matrix
{
static int n;
ll a[N][N];
Matrix(ll k=0)
{
for(int i=0; i<n; ++i)fill(a[i],a[i]+n,0),a[i][i]=k;
}
ll* operator[](int n)
{
return a[n];
}
};
int Matrix::n=N;
Matrix operator*(const Matrix &a,const Matrix &b)
{
Matrix r(0);
for(int i=0; i<r.n; ++i)
for(int j=0; j<r.n; ++j)
for(int k=0; k<r.n; ++k)
r.a[i][j]=(r.a[i][j]+mul(a.a[i][k],b.a[k][j],M))%M;
return r;
}
Matrix pow(Matrix a,ll b)
{
Matrix r(1);
for(; b; b>>=1,a=a*a)
if(b&1)r=r*a;
return r;
}
int main()
{
ll t,n,ans;
for(scanf("%lld",&t); t--;)
{
scanf("%lld",&n);
if(n<3)
{
printf("%d\n",n==1?3:9);
continue;
}
Matrix A,P;
for(int i=0; i<N; ++i)A[i][0]=1;
P[0][3]=P[0][6]=1;
P[1][0]=P[1][3]=P[1][6]=1;
P[2][0]=P[2][3]=1;
P[3][1]=P[3][4]=P[3][7]=1;
P[4][1]=P[4][7]=1;
P[5][1]=P[5][4]=1;
P[6][5]=P[6][8]=1;
P[7][2]=P[7][8]=1;
P[8][2]=P[8][5]=1;
A=pow(P,n-2)*A;
for(int i=ans=0; i<N; ++i)ans=(ans+A[i][0])%M;
printf("%lld\n",ans);
}
}