ACM-ICPC 2018 焦作赛区网络预赛

Diposting di | Edited on

传送门

A. Magic Mirror

题意

签到题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pp pair<int,int>
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
string s;
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        cin>>s;
        for(int i=0;i<s.length();i++){
            if(s[i]<='Z'&&s[i]>='A'){
                s[i]+=32;
            }
        }
        if(s=="jessie"||s=="jessie"){
            cout<<"Good guy!"<<endl;
        }
        else{
            cout<<"Dare you say that again?"<<endl;
        }
    }
    return 0;
}

B. Mathematical Curse

题意

有一个包含n个非零整数的序列和一个含有m个字符的字符串s，字符只可能是 ‘+’, ‘-‘, ‘*’, ‘/‘ 四种，有一个初始值 k

现要从序列中取出一个含有m个数的子序列{a1, a2, .. , am}，求 k 和 m 个数进行运算后的最大值

要按照原序列的顺序进行运算

如：

4 4 5

1 2 3 4

+-*/

ans = ((((5 + 1) - 2) * 3) / 4)

思路

solve by lx

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <bits/stdc++.h>

using namespace std;

const int mod=1000000007;
#define inf 0x3f3f3f3f3f

long long a[1010];
char f[10];

long long zma[10],zmi[10];

int main()
{
    int t,n,m;
    long long k;
    cin>>t;
    while(t--)
    {
            for(int i=0;i<10;i++)
            {
                    zma[i]=-1e18;
                    zmi[i]=1e18;
            }
            cin>>n>>m>>k;
            for(int i=1;i<=n;i++)
            {
                    cin>>a[i];
            }
                cin>>f;
            for(int i=1;i<=m;i++)
            {
                    for(int j=i-1;j>=0;j--)
                    {
                            long long x1,x2,now1,now2;
                            if(j>0)
                            {
                                    x1=zma[j-1];
                                    x2=zmi[j-1];
                            }
                            else
                            {
                                    x1=k;
                                    x2=k;
                            }

                            if(f[j]=='+')
                            {
                                    now1=x1+a[i];
                                    now2=x2+a[i];
                            }
                            else if(f[j]=='-')
                            {
                                    now2=x2-a[i];
                                    now1=x1-a[i];
                            }
                            else if(f[j]=='*')
                            {
                                    now1=x1*a[i];
                                    now2=x2*a[i];
                            }
                            else if(f[j]=='/')
                            {
                                    now1=x1/a[i];
                                    now2=x2/a[i];
                            }
                            if(now1>zma[j])
                                zma[j]=now1;
                            if(now1<zmi[j])
                                zmi[j]=now1;
                            if(now2>zma[j])
                                zma[j]=now2;
                            if(now2<zmi[j])
                                zmi[j]=now2;
                    }
            }
            for(int i=m+1;i<=n;i++)
            {
                    for(int j=m-1;j>=0;j--)
                    {
                            long long x1,x2,now1,now2;
                            if(j>0)
                            {
                                    x1=zma[j-1];
                                    x2=zmi[j-1];
                            }
                            else
                            {
                                    x1=k;
                                    x2=k;
                            }

                            if(f[j]=='+')
                            {
                                    now1=x1+a[i];
                                    now2=x2+a[i];
                            }
                            else if(f[j]=='-')
                            {
                                    now2=x2-a[i];
                                    now1=x1-a[i];
                            }
                            else if(f[j]=='*')
                            {
                                    now1=x1*a[i];
                                    now2=x2*a[i];
                            }
                            else if(f[j]=='/')
                            {
                                    now1=x1/a[i];
                                    now2=x2/a[i];
                            }
                            if(now1>zma[j])
                                zma[j]=now1;
                            if(now1<zmi[j])
                                zmi[j]=now1;
                            if(now2>zma[j])
                                zma[j]=now2;
                            if(now2<zmi[j])
                                zmi[j]=now2;
                    }
            }
            cout<<zma[m-1]<<endl;
    }
    return 0;
}

/*
100
5 5 1000
1000 1000 1000 1000 1000
*****
*/

G. Give Candies

题意

1
给n个小孩发糖果，总共有n个糖果，小孩按顺序排好，把糖果分发，不必每个小孩都有糖果，但是如果不是每个孩子都有糖果，那么只能是在后面的小孩没有糖果。问有多少种方案。

题解

就是往n个东西中间插任意个板子，所以最多能插n - 1个，所以答案为2^(n - 1) % p。但是n最大有1e5位数，所以要用小费马定理化简。

假如p是质数，且gcd(a,p)=1，那么

a^(p-1) ≡1（mod p）

我们可以利用费马小定理来简化幂模运算：由于a^(p-1)≡a^0≡1(mod p)，所以a^x(mod p)有循环节，长度为p-1，所以a^x≡a^(x%(p-1))(mod p)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pp pair<int,int>
const ll mod=1e9+7;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
string s;
ll poww(ll b){
    ll ans=1,base=2;
    while(b){
        if(b&1)ans=(ans*base)%mod;
        base=(base*base)%mod;
        b/=2;
    }
    return ans;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        cin>>s;
        int len=s.length();
        ll num=0;
        for(int i=0;i<len;i++){
            num=((num*10)+(s[i]-'0'))%(mod-1);
        }
        num-=1;
        cout<<poww(num)<<endl;
    }
    return 0;
}

H. String and Times

题意

求子串出现次数在k1=<num<=k2;

题解

https://blog.csdn.net/calabash_boy/article/details/77959704

抄了葫芦娃的这篇博客直接1A 太强了

1
2
3
4
5
恰好k次 = 至少k次 - 至少k+1次。答案转化为求至少出现k次的子串个数统计。构造好后缀数组以及很重要的Height数组之后。用一个k-1的窗子去滑动。窗子里边放着k-1个Height值（Height[ i+1 ]，Height[ i+2 ]，……，Height[ i+k ]），这样k-1个值就联系了k个后缀（SA[ i ]，SA[ i+1 ]，……，SA[ i+k ]），显然要求出这k-1个Height值的最小值，这个最小值就是这k个后缀的极大公共前缀了，假设是x，那么长度为1..x的前缀都在这个窗子里面出现了k次，也就是说他们都是符合答案的子串了。但是要考虑前边已经重复统计过了1..x中的一部分，考虑前一个窗子（Height[ i ]，Height[ i+1 ]，……，Height[ i+k-1 ]），讨论前面这个窗子的最小值y：1、y<x，那么说明上一个窗子的最小值一定是Height[ i ] ，因此上一个窗子统计了1..Height[ i ]部分，这一次需要统计Height[ i ]..x部分。2、y>x，那么就是说明前面窗子的极大公共前缀长度 比 这一个窗子的 极大公共前缀长，而这两个窗子有（i+1,i+2,，……,i+k-1）这k-2个元素是一样的。因此考虑所有的k个值（Height[ i ]，Height[ i+1 ]，……，Height[ i+k-1 ]，Height[ i+k ]），1..x必然是他们的公共前缀，那么由于y>x，前面一个窗子已经统计完了1..y的部分，1..x的部分被计算在前一个窗子里面了，这一次不需要计算，为了和上边一个式子统一起来，我们考虑Height[ i ]，显然有Height[ i ]>=y>x，进而有Height[ i ]>x。



因此结论是：用k-1的窗子从2开始滑动，维护窗子的最小值，然后每个窗子和刚刚移出窗子的那个Height作比较，如果min>Height，就统计min-Height。相反不统计。维护最小值用单调队列复杂度最低（priority_queue是nlogn，手写数组模拟是n）。构造后缀数组用倍增方法，复杂度是nlogn，因此整体复杂度是nlogn。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MaxN=1e5+100;
const int MAXN = MaxN;
ll cntA[MaxN],cntB[MaxN],tsa[MAXN],A[MAXN],B[MAXN];
ll sa[MAXN],Rank[MAXN],h[MAXN];
char ch[MAXN];
ll k1,k2;
struct Node{
	int val,index;
	Node(int val_,int index_):val(val_),index(index_){
	}
	bool operator < (const Node b)const{
		if (val==b.val){
			return b.index<index;
		}
		return b.val<val;
	}
};
priority_queue<Node>pq;
void GetSa(char *ch,ll *sa,ll *rank,ll n){

    for(int i=0;i<MaxN;i++)  cntA[i]=0;
    for(int i=1;i<=n;i++)   cntA[ch[i]]++;
    for(int i=1;i<=MaxN;i++) cntA[i]+=cntA[i-1];
    for(int i=n;i;i--)  sa[cntA[ch[i]]--]=i;
    rank[sa[1]]=1;
    for(int i=2;i<=n;i++){
        rank[sa[i]]=rank[sa[i-1]];
        if(ch[sa[i]]!=ch[sa[i-1]])  rank[sa[i]]++;
    }
    for(int l=1;rank[sa[n]]<n;l<<=1){
        for(int i=0;i<MaxN;i++)  cntA[i]=0;
        for(int i=0;i<MaxN;i++)  cntB[i]=0;
        for(int i=1;i<=n;i++){
            cntA[A[i]=rank[i]]++;
            cntB[B[i]=(i+l<=n)?rank[i+l]:0]++;
        }
        for(int i=1;i<MaxN;i++)   cntB[i]+=cntB[i-1];
        for(int i=n;i;i--)  tsa[cntB[B[i]]--]=i;
        for(int i=1;i<MaxN;i++)  cntA[i]+=cntA[i-1];
        for(int i=n;i;i--)  sa[cntA[A[tsa[i]]]--]=tsa[i];
        rank[sa[1]]=1;
        for(int i=2;i<=n;i++){
            rank[sa[i]]=rank[sa[i-1]];
            if(A[sa[i]]!=A[sa[i-1]] || B[sa[i]]!=B[sa[i-1]])    rank[sa[i]]++;
        }
    }
}

void GetHeight(char *ch,ll *sa,ll *rank,ll *height,ll n){

    GetSa(ch,sa,rank,n);
    for(int i=1,j=0;i<=n;i++){
        if(j)   j--;
        while(ch[i+j]==ch[sa[rank[i]-1]+j]) j++;
        height[rank[i]]=j;
    }
}
ll GetK(ll k,ll n){
    ll ans=0;
    k--;
    if(k==0){
        for(int i=1;i<=n;++i)   ans=ans+(n-sa[i]+1-h[i]);
        return ans;
    }
	while (!pq.empty())pq.pop();
	for (int i=2;i<=n;i++){
		while (!pq.empty()&&pq.top().index<i-k+1)pq.pop();
		pq.push(Node(h[i],i));
		if (i>k){
			int top = pq.top().val;
			int last = h[i-k];
			ans +=max(0,top-last);
		}
	}
    return ans;
}

void Run(){
    ll n,k;
    while(~scanf("%s",ch+1)){
        scanf("%lld%lld",&k1,&k2);
        n=strlen(ch+1);
        GetHeight(ch,sa,Rank,h,n);
        printf("%lld\n",GetK(k1,n)-GetK(k2+1,n));
    }
}
int main(){
    Run();
    return 0;
}

I. Save the Room

题意

有一个abc大小的长方体，你用112大小的长方体来填充，填充过程中，不能超出abc长方体的空间。问是否可以刚好填充。

题解

因为是1×1×2大小，所以以1×1为底面填充一定可以把底面填满，那么只需要考虑高就好啦，然后发现，高是二的倍数就可以刚好填充。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pp pair<int,int>
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
string s;
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int a,b,c;
    while(cin>>a>>b>>c){
        if(a%2==0||b%2==0||c%2==0)cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}

J. Participate in E-sports

题意

让你分别判断n或（n-1）*n/2是否是完全平方数。

题解

大数开方，可以二分或者牛顿迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
import java.math.BigInteger;
import java.util.Scanner;

public class Main{
	static BigInteger cal(BigInteger x){
        BigInteger l = BigInteger.ONE ;
        BigInteger r = x ;
        BigInteger temp = BigInteger.ZERO ;
        while(!l.equals(r)){
            BigInteger mid = (l.add(r)).divide(BigInteger.valueOf(2)) ;
            if(temp.compareTo(BigInteger.ZERO)!=0&&temp.compareTo(mid)==0){
                break ;
            }else{
                temp = mid ;
            }
            if(temp.compareTo(BigInteger.ZERO)==0){
                temp = mid ;
            }
            if(mid.multiply(mid).compareTo(x)==1){
                r=mid ;
            }else{
                l=mid ;
            }
        }
        if(l.multiply(l).compareTo(x)==1){
            l=l.subtract(BigInteger.ONE) ;
        }
        return l;
        
    }
	public static void main(String[] args) {
		int T;
		Scanner cin=new Scanner(System.in);
		T=cin.nextInt();
		BigInteger a = BigInteger.ZERO ;	
		BigInteger b =BigInteger.ZERO ;	
		BigInteger tmp = BigInteger.ZERO  ;
		boolean flag1=false,flag2=false;
		while((T--)>0) {
			flag1=false;
			flag2=false;
			a=cin.nextBigInteger();
			tmp=cal(a);
			if(a.equals(BigInteger.ONE)){
	             System.out.println("Arena of Valor");
	               continue;
			}
			if(a.equals(BigInteger.valueOf(2))){
		          System.out.println("Clash Royale");
	               continue;
			}
			if(tmp.multiply(tmp).equals(a)){
				flag1=true;
			}
			if(a.mod(BigInteger.valueOf(2)).equals(BigInteger.ZERO)){
				BigInteger tmp1 = a.divide(BigInteger.valueOf(2));
                BigInteger tmp2 = a.subtract(BigInteger.ONE);
                BigInteger t1 = cal(tmp1);
                if (t1.multiply(t1).equals(tmp1)) {
                    BigInteger t2 = cal(tmp2);
                    if (t2.multiply(t2).equals(tmp2)) {
                        flag2 = true;
                    }
                }
			}
			else{
			     BigInteger tmp1 = a.subtract(BigInteger.ONE).divide(BigInteger.valueOf(2));
	                BigInteger t1 = cal(tmp1);
	                if (t1.multiply(t1).equals(tmp1)) {
	                    if(flag1 == true) {
	                        flag2 = true;
	                    }
	                }	
			}
			if(flag1==true&&flag2==true) {
				System.out.println("Arena of Valor");
			}
			else if(flag1==true&&flag2==false) {
				System.out.println("Hearth Stone");
			}
			else if(flag1==false&&flag2==true) {
				System.out.println("Clash Royale");
			}
			else{
				System.out.println("League of Legends");
			}
		}
	}
}

K. Transport Ship

题意

每个物品的大小为v有2^c-1个 q次询问 问你当背包容量为s的时候有多少种可行方案

题解

多重二进制背包，把每个容量变成二进制表示 比如2^3-1=8-1=7=={1,2,4};正好三次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pp pair<int,int>
const ll mod=1e9+7;
const int maxn=1e4+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
ll dp[10010];
int v[20],c[20];
int main()
{
   /* std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);*/
    int t;
    scanf("%d",&t);
    while(t--){
        int n,q;
        scanf("%d%d",&n,&q);
        memset(dp,0,sizeof(dp));
        dp[0]=1;
        int cc,vv;
        for(int i=0;i<n;i++){
            scanf("%d%d",&vv,&cc);
            int bit=1;
            for(int j=0;j<cc;j++){
                for(int k=10000;k>=bit*vv;k--){
                    dp[k]=(dp[k]+dp[k-bit*vv])%mod;
                }
                bit*=2;
            }
        }
        while(q--){
            int k;
            scanf("%d",&k);
            printf("%lld\n",dp[k]);
        }
    }
    return 0;
}

L. Poor God Water

题意

有肉，鱼，巧克力三种食物，有几种禁忌，对于连续的三个食物，1.这三个食物不能都相同；2.若三种食物都有的情况，巧克力不能在中间；3.如果两边是巧克力，中间不能是肉或鱼，求方案数

题解

这题类似于AC自动机的POJ-2778-病毒串问题，把不能的禁忌当成坏的子串然后用ac自动机得出矩阵后进行矩阵快速幂

不过一开始ac自动机过不去，就得出十组数据搞进BM里面了后面矩阵优化一下直接300ms过去了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <bits/stdc++.h>

using namespace std;
#define rep(i,a,n) for (long long i=a;i<n;i++)
#define per(i,a,n) for (long long i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((long long)(x).size())
typedef vector<long long> VI;
typedef long long ll;
typedef pair<long long,long long> PII;
const ll mod=1e9+7;
ll powmod(ll a,ll b){
    ll res=1;
    a%=mod;
 //   assert(b>=0);
    for(;b;b>>=1)
    {
    if(b&1)
    res=res*a%mod;
    a=a*a%mod;
    }
    return res;
}
// head

long long _,n;
namespace linear_seq
{
    const long long N=10010;
    ll res[N],base[N],_c[N],_md[N];

    vector<long long> Md;
    void mul(ll *a,ll *b,long long k)
    {
        rep(i,0,k+k) _c[i]=0;
        rep(i,0,k) if (a[i]) rep(j,0,k)
            _c[i+j]=(_c[i+j]+a[i]*b[j])%mod;
        for (long long i=k+k-1;i>=k;i--) if (_c[i])
            rep(j,0,SZ(Md)) _c[i-k+Md[j]]=(_c[i-k+Md[j]]-_c[i]*_md[Md[j]])%mod;
        rep(i,0,k) a[i]=_c[i];
    }
    long long solve(ll n,VI a,VI b)
    { // a 系数 b 初值 b[n+1]=a[0]*b[n]+...
//        printf("%d\n",SZ(b));
        ll ans=0,pnt=0;
        long long k=SZ(a);
   //     assert(SZ(a)==SZ(b));
        rep(i,0,k) _md[k-1-i]=-a[i];_md[k]=1;
        Md.clear();
        rep(i,0,k) if (_md[i]!=0) Md.push_back(i);
        rep(i,0,k) res[i]=base[i]=0;
        res[0]=1;
        while ((1ll<<pnt)<=n) pnt++;
        for (long long p=pnt;p>=0;p--)
        {
            mul(res,res,k);
            if ((n>>p)&1)
            {
                for (long long i=k-1;i>=0;i--) res[i+1]=res[i];res[0]=0;
                rep(j,0,SZ(Md)) res[Md[j]]=(res[Md[j]]-res[k]*_md[Md[j]])%mod;
            }
        }
        rep(i,0,k) ans=(ans+res[i]*b[i])%mod;
        if (ans<0) ans+=mod;
        return ans;
    }
    VI BM(VI s)
    {
        VI C(1,1),B(1,1);
        long long L=0,m=1,b=1;
        rep(n,0,SZ(s))
        {
            ll d=0;
            rep(i,0,L+1) d=(d+(ll)C[i]*s[n-i])%mod;
            if (d==0) ++m;
            else if (2*L<=n)
            {
                VI T=C;
                ll c=mod-d*powmod(b,mod-2)%mod;
                while (SZ(C)<SZ(B)+m) C.pb(0);
                rep(i,0,SZ(B)) C[i+m]=(C[i+m]+c*B[i])%mod;
                L=n+1-L; B=T; b=d; m=1;
            }
            else
            {
                ll c=mod-d*powmod(b,mod-2)%mod;
                while (SZ(C)<SZ(B)+m) C.pb(0);
                rep(i,0,SZ(B)) C[i+m]=(C[i+m]+c*B[i])%mod;
                ++m;
            }
        }
        return C;
    }
    long long gao(VI a,ll n)
    {
        VI c=BM(a);
        c.erase(c.begin());
        rep(i,0,SZ(c)) c[i]=(mod-c[i])%mod;
        return solve(n,c,VI(a.begin(),a.begin()+SZ(c)));
    }
};

int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
    scanf("%lld",&n);
       printf("%lld\n",linear_seq::gao(VI{3,9,20,46,106,244,560,1286,2956,6794},n-1));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include<algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include  <stdio.h>
#include   <math.h>
#include   <time.h>
#include   <vector>
#include   <bitset>
#include    <queue>
#include      <map>
#include      <set>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=10*10+5;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
struct Matrix{
    unsigned long long mat[maxn][maxn];
    int n;
    Matrix(){}
    Matrix(int _n){
        n=_n;
        for(int i=0;i<n;i++)for(int j=0;j<n;j++)mat[i][j]=0;
    }
    Matrix operator *(const Matrix &b)const{
        Matrix ret=Matrix(n);
        for(int i=0;i<n;i++){
            for(int k=0;k<n;k++){
                if(mat[i][k])
                for(int j=0;j<n;j++){
                    ret.mat[i][j]+=(mat[i][k]*b.mat[k][j])%mod;
                    ret.mat[i][j]%=mod;
                }
            }
        }
        return ret;
    }
    unsigned long long pow_m(unsigned long long a,int n){
        unsigned long long ret=1,tmp=a;
        while(n){
            if(n&1)ret*=tmp;
            tmp*=tmp;
            n>>=1;
        }return ret;
    }
    Matrix pow_M(Matrix a,ll n){
        Matrix ret=Matrix(a.n);
        for(int i=0;i<a.n;i++)ret.mat[i][i]=1;
        Matrix tmp=a;
        while(n){
            if(n&1)ret=ret*tmp;
            tmp=tmp*tmp;
            n>>=1;
        }
        return ret;
    }
};
struct Trie{
    int next[maxn][3],fail[maxn],id['z'+1];
    bool end[maxn];
    int root,L;
    int newnode(){
        for(int i=0;i<3;++i)next[L][i]=-1;
        end[L++]=false;
        return L-1;
    }
    void init(){
        L=0;
        id['a']=0;id['b']=1;id['c']=2;
        root=newnode();
    }
    void insert(char buf[]){
        int len=strlen(buf);
        int now=root;
        for(int i=0;i<len;i++){
            if(next[now][id[buf[i]]]==-1)next[now][id[buf[i]]]=newnode();
            now=next[now][id[buf[i]]];
        }
        end[now]=true;
    }
    void build(){
        queue<int>Q;
        fail[root]=root;
        for(int i=0;i<3;i++)
            if(next[root][i]==-1)next[root][i]=root;
            else{
                fail[next[root][i]]=root;
                Q.push(next[root][i]);
            }
        while(!Q.empty()){
            int now=Q.front();
            Q.pop();
            if(end[fail[now]])end[now]=true;
            for(int i=0;i<3;i++)
                if(next[now][i]==-1)
                    next[now][i]=next[fail[now]][i];
                else{
                    fail[next[now][i]]=next[fail[now]][i];
                    Q.push(next[now][i]);
                }
        }
    }
    Matrix getMatrix(){
        Matrix ret=Matrix(L);
        for(int i=0;i<L;i++){
            for(int j=0;j<3;j++){
                if(end[next[i][j]]==false&&end[i]==false)
                    ret.mat[i][next[i][j]]++;
            }
        }
        return ret;
    }

};
Trie ac;
char buf[9][4]={"aaa","bbb","ccc","acb","bca","cac","cbc"};
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);

    ac.init();
    for(int i=0;i<7;i++){
        ac.insert(buf[i]);
    }
    ac.build();
    int t;
    cin>>t;
    Matrix mat=ac.getMatrix();
    while(t--){
        ll L;
        cin>>L;

        Matrix matt=mat.pow_M(mat,L);
        ll ans=0;
        for(int i=0;i<matt.n;i++){
            ans=(ans+matt.mat[0][i])%mod;
        }
        cout<<ans<<endl;
    }
    return 0;
}