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

A. Magic Mirror

水。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 int t;
 5 char s[100];
 6 
 7 inline bool work()
 8 {
 9     int len = strlen(s);
10     if (len != 6) return false;
11     if (s[0] != 'j' && s[0] != 'J') return false;
12     if (s[1] != 'e' && s[1] != 'E') return false;
13     if (s[2] != 's' && s[2] != 'S') return false;
14     if (s[3] != 's' && s[3] != 'S') return false;
15     if (s[4] != 'i' && s[4] != 'I') return false;
16     if (s[5] != 'e' && s[5] != 'E') return false;
17     return true;
18 }
19 
20 inline void Run() 
21 {
22     scanf("%d", &t);
23     while (t--)
24     {
25         scanf("%s", s);
26         puts(work() ? "Good guy!" : "Dare you say that again?");
27     }
28 }
29 
30 int main()
31 {
32     #ifdef LOCAL  
33         freopen("Test.in", "r", stdin);    
34     #endif   
35 
36     Run();  
37     return 0;  
38 }

View Code

B. Mathematical Curse

题意：有n个房间,m个诅咒，每个房间有一个数值，刚开始有一个初始值，每次进入一个房间可以选择消除诅咒或者不消除，消除诅咒只能顺序消除，消除诅咒就是拿初始值和房间的数值做运算，求最后最大的数是多少

思路：$Max[i][j]$ 表示第i个房间第j个操作的最大值, $Min[i][j]$ 表示第i个房间第j个操作的最小值

因为乘法负负相乘可能变得很大

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define N 1010
 5 #define ll long long 
 6 #define INFLL 0x3f3f3f3f3f3f3f3f
 7 
 8 int t, n, m;
 9 int arr[N];
10 char f[10];
11 ll Max[N][10], Min[N][10]; 
12 ll k, ans;
13 
14 inline void Run() 
15 {
16     scanf("%d", &t);
17     while (t--)
18     {
19         scanf("%d%d%lld", &n, &m, &k);
20         for (int i = 1; i <= n; ++i) scanf("%d", arr + i);
21         scanf("%s", f + 1);
22         memset(Max, -0x3f, sizeof Max);
23         memset(Min, 0x3f, sizeof Min);
24         Max[0][0] = Min[0][0] = k; ans = -INFLL; 
25         for (int i = 1; i <= n; ++i)
26         {
27             Max[i][0] = k, Min[i][0] = k;
28             for (int j = 1; j <= min(m, i); ++j) 
29             {
30                 Max[i][j] = Max[i - 1][j], Min[i][j] = Min[i - 1][j]; 
31                 ll a = Max[i - 1][j - 1], c = Min[i - 1][j - 1], b = (ll)arr[i];
32                 if (f[j] == '+')
33                 {
34                     a += b, c += b;
35                 }
36                 else if (f[j] == '-')
37                 {
38                     a -= b, c -= b;
39                 }
40                 else if (f[j] == '*')
41                 {
42                     a *= b, c *= b; 
43                 }
44                 else if (f[j] == '/')
45                 {
46                     a /= b, c /= b;  
47                 }
48                 if (a < c) swap(a, c); 
49                 Max[i][j] = max(Max[i][j], a);
50                 Min[i][j] = min(Min[i][j], c); 
51                 //printf("%d %d %lld %lld
", i, j, Max[i][j], Min[i][j]);
52             }
53             ans = max(ans, Max[i][m]);  
54         }
55         printf("%lld
", ans);
56     }
57 }
58 
59 int main()
60 {
61     #ifdef LOCAL  
62         freopen("Test.in", "r", stdin);    
63     #endif   
64 
65     Run();  
66     return 0;  
67 }

View Code

C. Password

留坑。

D. Sequence

留坑。

E. Jiu Yuan Wants to Eat

题意：四种操作。

思路：将取反看成加法和乘法例如：Not(1000) = 1111 - 1000

然后树链剖分维护 + 线段树

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 
  4 #define N 100010
  5 #define ull unsigned long long
  6 
  7 const ull D = 18446744073709551615;
  8 
  9 struct Edge
 10 {
 11     int to, nx;
 12     inline Edge() {}
 13     inline Edge(int to, int nx) : to(to), nx(nx) {}
 14 }edge[N << 1];
 15 
 16 int n, q;
 17 int head[N], pos;
 18 int top[N], fa[N], deep[N], num[N], p[N], fp[N], son[N], tot;
 19 
 20 inline void Init()
 21 {
 22     memset(head, -1, sizeof head); pos = 0;
 23     memset(son, -1, sizeof son); tot = 0;
 24     fa[1] = 1; deep[1] = 0;
 25 }
 26 
 27 inline void addedge(int u, int v)
 28 {
 29     edge[++pos] = Edge(v, head[u]); head[u] = pos; 
 30 }
 31 
 32 inline void DFS(int u)
 33 {
 34     num[u] = 1;
 35     for (int it = head[u]; ~it; it = edge[it].nx)
 36     {
 37         int v = edge[it].to;
 38         if (v == fa[u]) continue;
 39         fa[v] = u; deep[v] = deep[u] + 1;
 40         DFS(v); num[u] += num[v];
 41         if (son[u] == -1 || num[v] > num[son[u]]) son[u] = v;
 42     }
 43 }
 44 
 45 inline void getpos(int u, int sp)
 46 {
 47     top[u] = sp;
 48     p[u] = ++tot;
 49     fp[tot] = u;
 50     if (son[u] == -1) return;
 51     getpos(son[u], sp);
 52     for (int it = head[u]; ~it; it = edge[it].nx)
 53     {
 54         int v = edge[it].to;
 55         if (v != son[u] && v != fa[u])
 56             getpos(v, v);
 57     }
 58 }
 59 
 60 struct node 
 61 {
 62     int l, r;
 63     ull sum, lazy[2]; 
 64     inline node() {}
 65     inline node(int _l, int _r)
 66     {
 67         l = _l, r = _r;
 68         sum = 0;
 69         lazy[0] = 0, lazy[1] = 1;  
 70     }
 71 }tree[N << 2];
 72 
 73 inline void pushup(int id)
 74 {
 75     tree[id].sum = tree[id << 1].sum + tree[id << 1 | 1].sum;   
 76 }
 77 
 78 inline void work0(node &r, ull lazy)  
 79 {
 80     
 81     r.sum = r.sum + lazy * (r.r - r.l + 1);
 82     r.lazy[0] = r.lazy[0] + lazy;  
 83 }
 84 
 85 inline void work1(node &r, ull lazy) 
 86 {
 87     r.sum = r.sum * lazy;
 88     r.lazy[0] = r.lazy[0] * lazy;
 89     r.lazy[1] *= lazy; 
 90 }
 91 
 92 inline void pushdown(int id)
 93 {
 94     if (tree[id].l >= tree[id].r) return;
 95     if (tree[id].lazy[1] != 1) 
 96     {
 97         ull lazy = tree[id].lazy[1]; tree[id].lazy[1] = 1;
 98         work1(tree[id << 1], lazy);
 99         work1(tree[id << 1 | 1], lazy);
100     }
101     if (tree[id].lazy[0])
102     {
103         ull lazy = tree[id].lazy[0]; tree[id].lazy[0] = 0;
104         work0(tree[id << 1], lazy);
105         work0(tree[id << 1 | 1], lazy);
106     }
107 }
108 
109 inline void build(int id, int l, int r)
110 {
111     tree[id] = node(l, r);
112     if (l == r) return;
113     int mid = (l + r) >> 1;
114     build(id << 1, l, mid);
115     build(id << 1 | 1, mid + 1, r);
116 }
117 
118 inline void update(int id, int l, int r, int vis, ull val)
119 {
120     if (tree[id].l >= l && tree[id].r <= r)
121     {
122         if (vis == 0)
123             work1(tree[id], val);
124         else
125             work0(tree[id], val);
126         return;
127     }
128     pushdown(id);
129     int mid = (tree[id].l + tree[id].r) >> 1;
130     if (l <= mid) update(id << 1, l, r, vis, val);
131     if (r > mid) update(id << 1 | 1, l, r, vis, val);
132     pushup(id);
133 }
134 
135 ull anssum;
136 
137 inline void query(int id, int l, int r)
138 {
139     if (tree[id].l >= l && tree[id].r <= r) 
140     {
141         anssum += tree[id].sum; 
142         return; 
143     }
144     pushdown(id);
145     int mid = (tree[id].l + tree[id].r) >> 1; 
146     if (l <= mid) query(id << 1, l, r);
147     if (r > mid) query(id << 1 | 1, l, r); 
148     pushup(id);
149 }
150 
151 inline void change(int u, int v, int vis, ull val)
152 {
153     int fu = top[u], fv = top[v]; 
154     while (fu != fv)
155     {
156         if (deep[fu] < deep[fv])
157         {
158             swap(fu, fv);
159             swap(u, v);
160         }
161         update(1, p[fu], p[u], vis, val);
162         u = fa[fu]; fu = top[u];
163     }
164     if (deep[u] > deep[v]) swap(u, v); 
165     update(1, p[u], p[v], vis, val); 
166 }
167 
168 inline void sum(int u, int v)
169 {
170     int fu = top[u], fv = top[v];
171     anssum = 0;
172     while (fu != fv)
173     {
174         if (deep[fu] < deep[fv])
175         {
176             swap(fu, fv);
177             swap(u, v);
178         }
179         query(1, p[fu], p[u]);
180         u = fa[fu], fu = top[u];
181     }
182     if (deep[u] > deep[v]) swap(u, v);
183     query(1, p[u], p[v]);
184 }
185 
186 inline void Run() 
187 {
188     while (scanf("%d", &n) != EOF)
189     {
190         Init();
191         for (int i = 2, u; i <= n; ++i)
192         {
193             scanf("%d", &u);
194             addedge(u, i);
195         }
196         DFS(1); getpos(1, 1); build(1, 1, n); 
197         scanf("%d", &q);
198         int op, u, v; ull val;
199         for (int i = 1; i <= q; ++i)
200         {
201             scanf("%d%d%d", &op, &u, &v);
202             if (op <= 2)
203             {
204                 scanf("%llu", &val);
205                 change(u, v, op - 1, val);
206             }
207             else if (op == 3)
208             {
209                 change(u, v, 0, -1);
210                 change(u, v, 1, D); 
211             }
212             else
213             {
214                 sum(u, v);
215                 printf("%llu
", anssum);
216             }
217         }
218     }
219 }
220 
221 int main()
222 {
223     #ifdef LOCAL  
224         freopen("Test.in", "r", stdin);    
225     #endif   
226 
227     Run();  
228     return 0;  
229 }

View Code

F. Modular Production Line

留坑。

G. Give Candies

题意：有n颗糖，有n个人，按顺序出列，每次随机给那个人一些糖（至少一颗），分完为止，求有多少方案

思路：规律是$2^{n - 1}$ 根据费马小定理 $a^{p - 1} = 1 pmod p$ 那么只要先用 $(n - 1) mod (MOD - 1)$ 再快速幂

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cmath>
 5 #include<cstring>
 6 #include<map>
 7 
 8 using namespace std;
 9 
10 typedef long long ll;
11 
12 const int MOD = (int)1e9 + 7;
13 const int INF = 0x3f3f3f3f;
14 const int maxn = (int)1e5 + 10;
15 
16 inline ll qpow(ll n, ll x)
17 {
18     ll res = 1;
19     while (n)
20     {
21         if (n & 1) res = (res * x) % MOD;
22         x = (x*x) % MOD;
23         n >>= 1;
24     }
25     return res;
26 }
27 
28 int t;
29 char str[maxn];
30 
31 inline void RUN()
32 {
33     scanf("%d", &t);
34     while (t--)
35     {
36         scanf("%s", str);
37         ll n = 0;
38         int len = strlen(str);
39         for (int i = 0; i < len; ++i)
40         {
41             n = n * 10 + str[i] - '0';
42             n %= (MOD - 1);
43         }
44         n = (n - 1 + (MOD - 1)) % (MOD - 1);
45         //cout << n << endl;
46         ll ans = qpow(n, 2);
47         printf("%lld
", ans);
48     }
49 }
50 
51 int main()
52 {
53 #ifdef LOCAL_JUDGE
54     freopen("Text.txt", "r", stdin);
55 #endif // LOCAL_JUDGE
56 
57     RUN();
58 
59 #ifdef LOCAL_JUDGE
60     fclose(stdin);
61 #endif // LOCAL_JUDGE
62 
63 }

View Code

H. String and Times

题意：求出有多少子串的出现次数在[A, B] 之间

思路：后缀自动机，出现次数至少为A 的减去出现次数知道为B + 1

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define ll long long
 5 #define N 200010
 6 
 7 char s[N];
 8 
 9 struct SAM {
10     int p, q, np, nq, cnt, lst, a[N][26], l[N], f[N], tot;
11     int Tr(char c) { return c - 'A'; }
12     int val(int c) { return l[c] - l[f[c]]; }
13     SAM() { cnt = 0; lst = ++cnt; }
14     void Initialize() {
15         memset(l, 0, sizeof(int)*(cnt + 1));
16         memset(f, 0, sizeof(int)*(cnt + 1));
17         for (int i = 0; i <= cnt; i++)for (int j = 0; j<26; j++)a[i][j] = 0;
18         cnt = 0; lst = ++cnt;
19     }
20     void extend(int c) {
21         p = lst; np = lst = ++cnt; l[np] = l[p] + 1;
22         while (!a[p][c] && p)a[p][c] = np, p = f[p];
23         if (!p) { f[np] = 1; }
24         else {
25             q = a[p][c];
26             if (l[p] + 1 == l[q])f[np] = q;
27             else {
28                 nq = ++cnt; l[nq] = l[p] + 1;
29                 memcpy(a[nq], a[q], sizeof(a[q]));
30                 f[nq] = f[q]; f[np] = f[q] = nq;
31                 while (a[p][c] == q)a[p][c] = nq, p = f[p];
32             }
33         }
34     }
35     int b[N], x[N], r[N];
36     void build() {
37         int len = strlen(s + 1);
38         for (int i = 1; i <= len; i++)extend(Tr(s[i]));
39         memset(r, 0, sizeof(int)*(cnt + 1));
40         memset(b, 0, sizeof(int)*(cnt + 1));
41         for (int i = 1; i <= cnt; i++)b[l[i]]++;
42         for (int i = 1; i <= len; i++)b[i] += b[i - 1];
43         for (int i = 1; i <= cnt; i++)x[b[l[i]]--] = i;
44         for (int i = p = 1; i <= len; i++) { p = a[p][Tr(s[i])]; r[p]++; }
45         for (int i = cnt; i; i--)r[f[x[i]]] += r[x[i]];
46     }
47     void solve() {
48         ll ans = 0; 
49         int A, B;
50         build();
51         scanf("%d %d", &A, &B);
52         // cnt 为不同子串个数   r[x[i]] 为第i个不同子串 出现的次数
53         for (int i = 1; i <= cnt; i++)if (r[x[i]] >= A) ans += val(x[i]);
54         for (int i = 1; i <= cnt; i++)if (r[x[i]] >= B + 1) ans -= val(x[i]);
55         printf("%lld
", ans);
56     }
57 }sam;
58 
59 inline void Run()
60 {
61     while (scanf("%s", s + 1) != EOF)
62     {
63         sam.Initialize();
64         sam.solve();
65     }
66 }
67 
68 int main()
69 {
70     #ifdef LOCAL  
71         freopen("Test.in", "r", stdin);
72     #endif    
73 
74     Run();
75     return 0;
76 }

View Code

I. Save the Room

水。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cmath>
 5 #include<cstring>
 6 #include<map>
 7 
 8 using namespace std;
 9 
10 typedef long long ll;
11 
12 const int MOD = (int)1e9 + 7;
13 const int INF = 0x3f3f3f3f;
14 const int maxn = (int)1e5 + 10;
15 
16 int a, b, c;
17 
18 inline void RUN()
19 {
20     while (~scanf("%d %d %d", &a, &b, &c))
21     {
22         if (a % 2 == 0 || b % 2 == 0 || c % 2 == 0)
23         {
24             puts("Yes");
25         }
26         else
27         {
28             puts("No");
29         }
30     }
31 }
32 
33 int main()
34 {
35 #ifdef LOCAL_JUDGE
36     freopen("Text.txt", "r", stdin);
37 #endif // LOCAL_JUDGE
38 
39     RUN();
40 
41 #ifdef LOCAL_JUDGE
42     fclose(stdin);
43 #endif // LOCAL_JUDGE
44 
45 }

View Code

J. Participate in E-sports

题意：判断$frac {(n - 1)(n)}{2}$ 和 $n$ 是不是平方数

思路：二分开方法

 1 import java.math.BigInteger;
 2 import java.util.Scanner;
 3 
 4 public class Main
 5 {
 6     public static BigInteger check(BigInteger n,BigInteger x) {
 7         BigInteger ans=BigInteger.valueOf(1);
 8         BigInteger a=BigInteger.valueOf(1);
 9         for(BigInteger i=BigInteger.ZERO;i.compareTo(n)<0;i=i.add(a)) {
10             ans=ans.multiply(x);
11         }
12         return ans;
13     }
14     static BigInteger Get(BigInteger m) {
15         BigInteger l=BigInteger.ZERO;
16         BigInteger a=BigInteger.valueOf(2);
17         BigInteger b=BigInteger.valueOf(1);
18         BigInteger r=BigInteger.valueOf(1);
19         BigInteger mid=BigInteger.ZERO;
20         while(check(BigInteger.valueOf(2),r).compareTo(m)<=0) {
21             l=r;
22             r=r.multiply(a);
23         }
24         while(l.compareTo(r)<=0) {
25             mid=l.add(r).divide(a);
26             if(check(BigInteger.valueOf(2),mid).compareTo(m)<=0) l=mid.add(b);
27             else r=mid.subtract(b);
28         }
29         return r;   //返回的是开方后的值
30     }
31 
32     public static boolean ok(BigInteger n)
33     {
34         BigInteger x = Get(n);
35         if (x.multiply(x).compareTo(n) == 0) return true;
36         return false;
37     }
38 
39     public static void main(String[] args)
40     {
41         Scanner in = new Scanner(System.in);
42         int t = in.nextInt();
43         for (int kase = 1; kase <= t; ++kase)
44         {
45 //            System.out.println("bug");
46             BigInteger n = in.nextBigInteger();
47             BigInteger nn = n.multiply(n.subtract(BigInteger.ONE)).divide(BigInteger.valueOf(2));
48             boolean flag[] = new boolean[2];
49             flag[0] = ok(n); flag[1] = ok(nn);
50             if (flag[0] && flag[1]) System.out.println("Arena of Valor");
51             else if (flag[0]) System.out.println("Hearth Stone");
52             else if (flag[1]) System.out.println("Clash Royale");
53             else System.out.println("League of Legends");
54         }
55         in.close();
56     }
57 }

View Code

K. Transport Ship

题意：有n种船，每种船有$v[i]$容量，每种船有$2^{c[i]} - 1$ 个，每次询问s，求能把s刚好装下的船的分配方案有多少

思路：多重背包+记录方案数

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define N 10010
 5 #define ll long long
 6 #define INF 0x3f3f3f3f
 7 
 8 const ll MOD = (ll)1e9 + 7; 
 9 
10 int Bit[30];
11 
12 inline void Init()
13 {
14     Bit[0] = 1;
15     for (int i = 1; i <= 20; ++i) Bit[i] = (Bit[i - 1] << 1);
16     for (int i = 1; i <= 20; ++i) --Bit[i];
17 }
18 
19 int t, n, q;
20 int v[30], c[30];
21 ll dp[N];
22 ll f[N];
23 
24 inline void Run() 
25 {
26     Init();
27     scanf("%d", &t);
28     while (t--)
29     {
30         scanf("%d%d", &n, &q);
31         for (int i = 1; i <= n; ++i)
32         {
33             scanf("%d%d", v + i, c + i);
34             c[i] = Bit[c[i]];
35         }
36         memset(f, 0, sizeof f);
37         dp[0] = 0; f[0] = 1; 
38         int m = 10000;
39         for (int i = 1; i <= m; ++i) dp[i] = -INF;
40         for (int i = 1; i <= n; ++i)
41         {
42             if (v[i] * c[i] >= m)
43             {
44                 for (int j = v[i]; j <= m; ++j) 
45                 {
46                     dp[j] = max(dp[j], dp[j - v[i]] + v[i]);
47                     if (dp[j] == dp[j - v[i]] + v[i])
48                         f[j] = (f[j] + f[j - v[i]]) % MOD;  
49                 } 
50             }
51             else
52             {
53                 int tmp = c[i];
54                 for (int k = 1; k < tmp; tmp -= k, k <<= 1)
55                 {
56                     for (int j = m; j >= k * v[i]; --j)
57                     {
58                         int w = k * v[i];
59                         dp[j] = max(dp[j], dp[j - w] + w);
60                         if (dp[j] == dp[j - w] + w)
61                             f[j] = (f[j] + f[j - w]) % MOD;
62                     }
63                 }
64                 for (int j = m; j >= tmp * v[i]; --j)
65                 {
66                     int w = tmp * v[i];
67                     dp[j] = max(dp[j], dp[j - w] + w);
68                     if (dp[j] == dp[j - w] + w)
69                         f[j] = (f[j] + f[j - w]) % MOD;
70                 }
71             }
72         }
73         for (int i = 1, id; i <= q; ++i)
74         {
75             scanf("%d", &id);
76             printf("%lld
", f[id]);
77         }
78     }
79 }
80 
81 int main()
82 {
83     #ifdef LOCAL  
84         freopen("Test.in", "r", stdin);    
85     #endif   
86 
87     Run();  
88     return 0;  
89 }

View Code

L. Poor God Water

线性递推

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 #define mst(a,b) memset((a),(b),sizeof(a))
  4 
  5 typedef long long ll;
  6 const int maxn = 10005;
  7 const ll mod = 1e9 + 7;
  8 const int INF = 0x3f3f3f3f;
  9 const double eps = 1e-9;
 10 
 11 
 12 ll fast_mod(ll a, ll n, ll Mod)
 13 {
 14     ll ans = 1;
 15     a %= Mod;
 16     while (n)
 17     {
 18         if (n & 1) ans = (ans*a) % Mod;
 19         a = (a*a) % Mod;
 20         n >>= 1;
 21     }
 22     return ans;
 23 }
 24 
 25 namespace Dup4
 26 {
 27     ll res[maxn], base[maxn], num[maxn], md[maxn];
 28     vector<int>vec;
 29     void mul(ll *a, ll *b, int k)
 30     {
 31         for (int i = 0; i < 2 * k; i++) num[i] = 0;
 32         for (int i = 0; i < k; i++)
 33         {
 34             if (a[i])
 35             {
 36                 for (int j = 0; j < k; j++)
 37                 {
 38                     num[i + j] = (num[i + j] + a[i] * b[j]) % mod;
 39                 }
 40             }
 41         }
 42         for (int i = 2 * k - 1; i >= k; i--)
 43         {
 44             if (num[i])
 45             {
 46                 for (int j = 0; j < vec.size(); j++)
 47                 {
 48                     num[i - k + vec[j]] = (num[i - k + vec[j]] - num[i] * md[vec[j]]) % mod;
 49                 }
 50             }
 51         }
 52         for (int i = 0; i < k; i++) a[i] = num[i];
 53     }
 54     ll solve(ll n, vector<int> a, vector<int> b)
 55     {
 56         ll ans = 0, cnt = 0;
 57         int k = a.size();
 58         assert(a.size() == b.size());
 59         for (int i = 0; i < k; i++) md[k - 1 - i] = -a[i];
 60         md[k] = 1;
 61         vec.clear();
 62         for (int i = 0; i < k; i++) if (md[i]) vec.push_back(i);
 63         for (int i = 0; i < k; i++) res[i] = base[i] = 0;
 64         res[0] = 1;
 65         while ((1LL << cnt) <= n) cnt++;
 66         for (int p = cnt; p >= 0; p--)
 67         {
 68             mul(res, res, k);
 69             if ((n >> p) & 1)
 70             {
 71                 for (int i = k - 1; i >= 0; i--) res[i + 1] = res[i];
 72                 res[0] = 0;
 73                 for (int j = 0; j < vec.size(); j++)
 74                 {
 75                     res[vec[j]] = (res[vec[j]] - res[k] * md[vec[j]]) % mod;
 76                 }
 77             }
 78         }
 79         for (int i = 0; i < k; i++) ans = (ans + res[i] * b[i]) % mod;
 80         if (ans < 0) ans += mod;
 81         return ans;
 82     }
 83     vector<int> BM(vector<int> s)
 84     {
 85         vector<int> B(1, 1), C(1, 1);
 86         int L = 0, m = 1, b = 1;
 87         for (int i = 0; i < s.size(); i++)
 88         {
 89             ll d = 0;
 90             for (int j = 0; j < L + 1; j++) d = (d + (ll)C[j] * s[i - j]) % mod;
 91             if (d == 0) m++;
 92             else if (2 * L <= i)
 93             {
 94                 vector<int> T = C;
 95                 ll c = mod - d * fast_mod(b, mod - 2, mod) % mod;
 96                 while (C.size() < B.size() + m) C.push_back(0);
 97                 for (int j = 0; j < B.size(); j++) C[j + m] = (C[j + m] + c * B[j]) % mod;
 98                 L = i + 1 - L, B = T, b = d, m = 1;
 99             }
100             else
101             {
102                 ll c = mod - d * fast_mod(b, mod - 2, mod) % mod;
103                 while (C.size() < B.size() + m) C.push_back(0);
104                 for (int j = 0; j < B.size(); j++) C[j + m] = (C[j + m] + c * B[j]) % mod;
105                 m++;
106             }
107         }
108         return C;
109     }
110     int gao(vector<int> a, ll n)
111     {
112         vector<int> c = BM(a);
113         c.erase(c.begin());
114         for (int i = 0; i < c.size(); i++) c[i] = (mod - c[i]) % mod;
115         return solve(n, c, vector<int>(a.begin(), a.begin() + c.size()));
116     }
117 }
118 
119 void RUN()
120 {
121     ll n;
122     int t;
123     scanf("%d", &t);
124     while(t--)
125     {
126         scanf("%lld", &n);
127         ++n;
128         printf("%d
", Dup4::gao(vector<int>{3,9,20,46,106,244,560,1286,2956,6794}, n - 2));
129     }
130 }
131 
132 int main()
133 {
134 #ifdef LOCAL_JUDGE
135     freopen("Text.txt", "r", stdin);
136 #endif // LOCAL_JUDGE
137 
138     RUN();
139 
140 #ifdef LOCAL_JUDGE
141     fclose(stdin);
142 #endif // LOCAL_JUDGE
143 
144 
145     return 0;
146 }

View Code