置换
题目描述
(negii) 沉迷于研究计算机的构造，他发现简单的二进制竟然能完成如此复杂的计算，当他知道二进制的所有位运算的操作之后，他突发奇想，他想找一种方法能实现二进制位的翻转。具体地，就是我们要将 (7(0111)) 翻转成 (14(1110))，(11(1011)) 翻转成 (13(1101)) 。
现在我们给定二进制位数 (k) 以及 (n) 个满足二进制位数不超过 (k) 的数，我们需要输出对应翻转后的数的十进制表示
由于读入量较大，所以 (n) 个数由本机随机生成，具体生成方式如下
int my_rand()
{
Seed=(214013LL*Seed+2531011)&((1<<k)-1);
return Seed;
}
我们会给出初始的 (Seed)，我们会调用 (n) 次函数，得到需要翻转的 (n) 个数
我们还会采取特殊的输出方式，我们将所有答案 (hash) ，并输出最后的值即可
int ans=0;
void my_hash(int x)
{
ans=((long long)ans*233+x)%99824353;
}
我们每得到一个数，进行翻转后，我们就会调用一次这个函数，其中传入参数 (x) 为翻转后的数，我们最后输出 (ans) 的值即可
输入格式
共 (3) 个数，分为 (n)，(k)，(Seed) 。
输出格式
一行，一个整数，表示最后 (hash) 值。
样例
样例输入
5 3 233
样例输出
76005766
数据范围与提示
对于前 (50\%) 的数据， (kleq 17)；
对于前 (70\%) 的数据， (kleq 20)；
对于前 (90\%) 的数据， (kleq 23)；
对于 (100\%) 的数据， (nleq 2^k ,kleq 25)；
思路
首先先理解一下题意吧，给你三个数，让你用上面的 (rand) 函数来造数据，其实它一点都不 (rand) ，多试几次就会发现，总会是那几个数，顺序都不带变的。
最后输出的时候，将每个翻转后的值 (hash) 一遍，输出 (ans) 即可。
这样我们就主要思考怎么翻转一个二进制的数了。
- 首先明确一个要点：(k) 表示的是一个数 (x) 转化成二进制的位数。
比如 (k=3) 时，(1) 转化为二进制为 (001) ，翻转后为 (100) ，即 (4) 。
(k=4) 时，(1) 转化为二进制为 (0001) ，翻转后为 (1000) ，即 (8) 。
这样我们就更加明确了题意。
怎么实现一个数的翻转呢？
比如我们要翻转 (0001011) 。
我们将它右移一位，变为 (000101) 。
如果我们知道了 (000101) 翻转后的数字，将它加上 (2^{k-1})，不就是我们要求的值了吗。
所以我们就可以用前面的将后面的值推出来。
for (int i = 1; i <= EJZ[25]; i++) {
if (i % 2 == 0) a[i] = a[i >> 1] >> 1;//如果最后一位为0,就不需要加上2^k-1
else a[i] = (a[i >> 1] >> 1) + EJZ[k - 1];//最后一位为1,需要加上2^k-1
}
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 4e7 + 50, mod = 99824353;
inline int read(){
int x = 0, w = 1;
char ch;
for (; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') w = -1;
for (; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
return x * w;
}
int EJZ[30]={1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304 ,8388608 , 16777216, 33554432, 67108864};
int n, k, Seed;
int a[maxn];
int my_rand(){
Seed = (214013LL * Seed + 2531011) & ((1 << k) - 1);
return Seed;
}
ll ans = 0;
void my_hash(int x){
ans = (ans * 233 + x) % mod;
}
int main(){
n = read(), k = read(), Seed = read();
for (int i = 1; i <= EJZ[25]; i++) {
if (i % 2 == 0) a[i] = a[i >> 1] >> 1;//如果最后一位为0,就不需要加上2^k-1
else a[i] = (a[i >> 1] >> 1) + EJZ[k - 1];//最后一位为1,需要加上2^k-1
}
for (int i = 1; i <= n; i++) {
int x = my_rand();
my_hash(a[x]);
}
printf("%lld
", ans);
return 0;
}
字符串
题目描述
(negii) 和 (starria) 是好朋友。他们在一起做字符串游戏。
我们定义对于一个字符串的翻转操作：比如翻转的串为 (R)，那么他会将前 (|R|−1) 个字符倒序后，插入到该串的最后。举个例子，串 (abd) 进行翻转操作后，将得到 (abdba) 。
(negii) 进行了若干次（可能为 (0) 次）字符串的翻转操作。
(negii) 对 (starria) 展示出了一个非空串 (S)， (S) 是一个串 (R) 的前缀。他想考考 (starria)，初始的串 (R) 的长度可能是多少。
(starria) 找到了正在参加模拟赛的你，请你来帮她解决这个问题。但聪明的 (starria) 发现，所有超过 (|S|) 的整数都一定是 (R) 的可能长度，因此你只需要告诉她不超过的 (|S|) 的 (R) 的可能长度即可。
输入格式
输入包含多组数据，第一行一个整数 (T) 表示数据组数。
接下来依次描述每组数据，对于每组数据，一行一个仅由小写字母组成的非空字符串 (S) 。
输出格式
对于每组数据，输出 (1) 行，从小到大输出 (|R|) 的所有不超过 (|S|) 的可能值，所有值之间用单个空格隔开。
样例
样例输入
3
abcdcb
qwqwq
qaqaqqq
样例输出
4 6
2 3 4 5
6 7
数据范围与提示
对于 (40\%) 的数据，保证 (sum |S|leq 5 imes 10^2) 。
对于 (60\%) 的数据，保证 (sum |S|leq 5 imes 10^3) 。
对于 (100\%) 的数据，保证 (|S|leq 10^6,sum |S|leq 5 imes 10^6) 。
思路
我们会发现：
- 当我们枚举后 (n/2) 的点时，我们向两边逐渐扩展：
若 (a[l]=a[r]) ，继续扩展，若 (r=n) 了，则证明这个点符合条件。
若 (a[l]!=a[r]) ，停止扩展，这个点也不会被记录到答案中。
- 当我们枚举前 (n/2) 的点时，我们也向两边扩展，不过跟上面不同的是，(l) 会先到达边界 (1)：
若 (a[l]=a[r]) ，继续扩展，若 (l=1) 了，并不能证明这个点是答案，需要判断当前走到的 (r) 点是否符合条件，若 (r) 点符合条件，这个点就是答案。
若 (a[l]!=a[r]) ，停止扩展，这个点也不会被记录到答案中。
- 如果我们用 (n^2) 直接去跑，肯定会 (TLE) ，所以我们需要借助一些效率比较高的算法。
法一
可以用一波 (hash)，维护一个正向的 (hash) 值，维护一个反向的 (hash) 值，比对正反 (hash) 值即可。
法二
可以用一波 (manacher)，记录下以每个节点为中心的回文长度，然后进行比较即可。
代码
法一
#include <bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int maxn = 1e6 + 5;
int T, n;
char a[maxn];
ull h[maxn], f[maxn], p[maxn];
ull H(int l, int r) {
return h[r] - h[l-1] * p[r-l+1];
}
ull F(int l, int r) {
return f[l] - f[r+1] * p[r-l+1];
}
int main() {
p[0] = 1;
for (int i = 1; i <= 1e6; ++i)
p[i] = p[i-1] * 131;
scanf("%d", &T);
while (T--) {
scanf("%s", a + 1);
n = strlen(a + 1);
f[n+1] = 0;
for (int i = 1; i <= n; ++i)//正向hash
h[i] = h[i-1] * 131 + a[i];
for (int i = n; i >= 1; --i)//反向hash
f[i] = f[i+1] * 131 + a[i];
for (int i = 2; i < n; ++i) {
int l = min(i, n - i + 1);
if (H(i - l + 1, i) != F(i, i + l - 1)) continue;
l = i-1 << 1;
if (l > n || H(1, n - l) == H(1 + l, n)) printf("%d ", i);
}
printf("%d
", n);
}
return 0;
}
法二
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e6 + 50, INF = 0x3f3f3f3f, mod = 1e9 + 7;
inline int read(){
int x = 0, w = 1;
char ch;
for (; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') w = -1;
for (; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
return x * w;
}
int T, n, tot, m;
char a[maxn];
char str[maxn];
bool flag[maxn];
int ans[maxn];
bool isblack[maxn];
void Init(){
str[1] = '$';
str[2] = '#';
for (int i = 1; i <= n; i++) {
str[i * 2 + 1] = a[i];
str[i * 2 + 2] = '#';
}
m = n * 2 + 2;
}
void manacher(){//经典manacher
int c = 0 ,r = 0;
for (int i = 1; i <= m; i++) {
if (r > i) {
ans[i] = min (ans[2 * c - i], r - i);
}else {
ans[i] = 1;
}
for (;str[i + ans[i]] == str[i - ans[i]]; ans[i]++);
if (ans[i] + i > r){
r = ans[i] + i;
c = i;
}
}
}
int l, r;
bool Judge(int k){
if(flag[k]) return isblack[k];
flag[k] = 1;
r = n - k + 1;
l = k;
if (l >= r) {//n/2以后的点
if (ans[2 * k + 1] / 2 >= r) {
isblack[k] = 1;
return 1;
}else {
isblack[k] = 0;
return 0;
}
}else {
if (ans[2 * k + 1] / 2 < l) {//n/2之前的点
isblack[k] = 0;
return 0;
}
isblack[k] = Judge(k + ans[2 * k + 1] / 2 - 1);
return isblack[k];
}
}
int main(){
T = read();
while (T--) {
tot = 0;
memset(isblack, 0, sizeof isblack);
memset(ans, 0, sizeof ans);
memset(flag, 0, sizeof flag);
scanf("%s", a + 1);
n = strlen(a + 1);
if(n==1){
printf("1
");
continue;
}
Init();
manacher();
for (int i = 2; i <= n; i++) {
if (!flag[i]) Judge(i);
}
for (int i = 1; i <= n; i++) {
if (isblack[i]) {
printf("%d ",i);
}
}
printf("
");
}
return 0;
}
饼干
题目描述
佩琪最喜欢吃饼干了！但是现在他不准备自己吃，她决定和贝茜分享自己的饼干。佩琪有四种口味的饼干，分别是巧克力味、香草味、红豆味和椰子味。可惜的是，佩琪已经把椰子味的饼干全吃光了，所以现在只剩下前三种了233。。。
巧克力味饼干能带来 (A) 的美味度，香草味饼干能带来 (B) 的美味度，而红豆味饼干可以带来 (A+B) 的美味度。
佩琪会拿出不多于 (N) 块饼干作为送给贝茜的礼物。
为了显得真诚，她想让她拿出的饼干的美味度之和恰好为 (K) 。
为了显得体面，她决定用一个精美的盒子来装这些饼干。盒子内部有 (N) 个位置，每个位置都可以放一块饼干，或者不放。
现在佩琪想知道有多少种方案可以既显得真诚又显得体面。两种方案不同，当且仅当盒子中某个位置放置的饼干味道不同，或者一个放了饼干而另一个没有。
佩琪自己当然不会做啦，所以她决定请你来帮她解决这个问题。为了防止答案过大，你只需要告诉她答案对 (998244353) 取模的结果就行了。
输入格式
输入只有一行，包含四个整数，分别为(N) 、(A) 、(B) 、(K) 。
输出格式
输出一行一个整数，即答案对 (998244353) 取模的结果。
样例
样例输入
4 1 2 5
样例输出
40
数据范围与提示
对于前 (30\%) 的数据，(1leq Nleq 10，0leq Kleq 500)；
对于前 (50\%) 的数据，(1leq Nleq 1000，0leq Kleq 3000)；
对于前 (80\%) 的数据，(1leq Nleq 1e5，0leq Kleq 2e10)；
对于 (100\%) 的数据，(1leq Nleq 1e7，0leq Kleq 1e15，0leq A,Bleq 1e5) 。
思路
- (30opts) 的分段
显然数据很小，可以直接走 (DFS) ,要么不放，要么放 (A)，要么放 (B)，要么放 (A+B) 。
- (50opts) 的分段
我们可以将 (DFS) 转为 (dp)，同样是四种决策，还可以用滚动数组，然而并没有什么卵用。
- (100opts) 的分段
数论预警！！！
我们可以发现 (A+B) 其实可以拆开，当作选一个 (A)，一个 (B)。
这样我们可以枚举 (A) 的个数 (i)，每次判断 (frac {k} {A} imes i) 是不是 (B) 的倍数，是，(ans+=C_n^i+C_n^{frac {frac{k}{A}*i} {B}}) 。
注意要判断特殊情况：
-
(A=0,B=0,k=0) 时，(ans=4^n)
-
(A eq 0,B eq 0,k=0) 时，(ans=1)
-
(A=0 / B=0,k=0) 时，(ans=2^n)
-
(A=0,B=0,k eq 0) 时，(ans=0)
-
(A=0 / B=0,k!=0) 时，设 (p=frac{k}{max(A,B)})，(ans=C_n^p imes 2^p imes 2^{n-p}=C_n^p imes 2^n)
代码
50opts dp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e7 + 50, INF = 0x3f3f3f3f, mod = 998244353;
inline int read(){
int x = 0, w = 1;
char ch;
for (; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') w = -1;
for (; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
return x * w;
}
int n, a, b, c, k;
ll f[2][maxn][4];
ll MOD(ll a, ll b){//快速模
if(a + b >= mod){
return a + b - mod;
}else {
return a + b;
}
}
int main(){
n = read(), a = read(), b = read(), k = read();
c = a + b;
f[0][0][0] = 1;
int s = 0;
for (register int i = 1; i <= n; i++) {
s = !s;
for (register int j = 0; j <= min(i * c, k); j++){
f[s][j][0] = f[s][j][1] = f[s][j][2] = f[s][j][3] = 0;
}
for (register int j = 0; j <= min(i * c, k); j++) {
f[s][j][0] = (f[s][j][0] + MOD(f[!s][j][0], f[!s][j][1]) + MOD(f[!s][j][2], f[!s][j][3])) % mod;
if (j >= a) f[s][j][1] = (f[s][j][1] + MOD(f[!s][j-a][0], f[!s][j-a][1]) + MOD(f[!s][j-a][2], f[!s][j-a][3])) % mod;
if (j >= b) f[s][j][2] = (f[s][j][2] + MOD(f[!s][j-b][0], f[!s][j-b][1]) + MOD(f[!s][j-b][2], f[!s][j-b][3])) % mod;
if (j >= c) f[s][j][3] = (f[s][j][3] + MOD(f[!s][j-c][0], f[!s][j-c][1]) + MOD(f[!s][j-c][2], f[!s][j-c][3])) % mod;
}
}
printf("%lld
", MOD(MOD(f[s][k][0], f[s][k][1]), MOD(f[s][k][2], f[s][k][3])));
return 0;
}
正解
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e7 + 50, INF = 0x3f3f3f3f, mod = 998244353;
inline int read(){
int x = 0, w = 1;
char ch;
for(; ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') w = -1;
for(; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
return x * w;
}
int n, a, b, k;
int ans;
int jc[maxn + 5], jcny[maxn + 5];
int qpow(int x, int y){//快速幂
int ans = 1;
while (y) {
if (y & 1) ans = ans * x % mod;
x = x * x % mod;
y >>= 1;
}
return ans;
}
int Ny(int x){//费马小定理求逆元
return qpow(x, mod - 2);
}
void Init(){
jc[0] = 1;
for (register int i = 1; i <= n; i++) {//求阶乘
jc[i] = (jc[i-1] * i) % mod;
}
}
int C(int a, int b){//组合数的计算
if (a == 0 || a < b) return 0;
if (b == 0) return 1;
else return jc[a] * Ny(jc[b]) % mod * Ny(jc[a-b]) % mod;
}
signed main(){
n = read(), a = read(), b = read(), k = read();
if (a == 0 && b == 0 && k != 0) {
printf("0
");
return 0;
}
if (a == 0 && b == 0 && k == 0) {
ans = 1;
for (int i = 1; i <= n; i++) {
ans = (ans * 4) % mod;
}
printf("%lld
", ans);
return 0;
}else if ((a == 0 || b == 0) && k == 0) {
ans = 1;
for (int i = 1; i <= n; i++) {
ans = (ans * 2) % mod;
}
printf("%lld
", ans);
return 0;
}
Init();
if (a == 0 || b == 0) {
int p = k / max(a, b);
ans = C(n, p);
for (int i = 1; i <= n; i++) {
ans = (ans * 2) % mod;
}
printf("%lld
", ans % mod);
return 0;
}
for (int i = 0; i <= n && a * i <= k; i++) {
if ((k - a * i) % b == 0 && (k - a * i) / b <= n) {
int j = (k - a * i) / b;
ans = (ans + C(n, i) * C(n, j)) % mod;
}
}
printf("%lld
", ans % mod);
return 0;
}
空间宝石
题目描述
(zP1nG) 很清楚自己打不过灭霸，所以只能在自己出的题里欺负他。
咳咳。这一次他得到了空间宝石 (Tesseract) 。
世界之树连接着九界，此时灭霸和 (zP1nG) 都在九界的某个地方。而九界是相互无法到达的。(zP1nG) 为了追杀灭霸，决定使用空间宝石的力量到达灭霸身边。因为 (zP1nG) 不擅长使用空间宝石，无法直接开一条从自己的位置到灭霸的位置的传送门，所以他只能无意识地使用空间宝石的力量。(zP1nG) 想知道，在自己胡乱地使用空间宝石后，通过传送门到达灭霸的位置最少需要多长时间。
具体地，九界的编号为 (0sim 8)，共有 (n) 道传送门，第 (i) 道传送门为优先级为 (p_i)，由 (u_i) 到 (v_i)，需要花费 (w_i) 个时间的单向门。传送的规则为：(zP1nG) 按顺序穿过的传送门的优先级必须是单调不降的。例如，(zP1nG) 穿过了三道传送门到达灭霸的位置，这三道传送门的优先级分别为 (1→2→2) 即为一种合法的方式，而优先级分别为 (1→2→1) 是不合法的。
(zP1nG) 会使用 (q) 次宝石的力量来尝试进行传送：其中第 (i) 次尝试会打开数道传送门，这些传送门的优先级会形成 (s_i) 个区间。例如，在某次尝试中 (zP1nG) 打开了三个区间 ([1,2],[4,7],[9,10])，那么优先级在这三个区间内的传送门将全部被打开并允许 (zP1nG) 穿过。你需要告诉 (zP1nG) 在此情况下从自己的位置 (z_i) 到达灭霸所在处 (t_i) 所需的最短时间。尝试结束后所有传送门会关闭。
输入格式
第 (1) 行包含两个正整数 (n) 和 (S)，(S) 的含义见数据范围与约定所述。
第 (2) 至 (n+1) 行每行包含 (4) 个正整数(p_i,u_i,v_i,w_i) 。
第 (n+2) 行包含一个正整数 (q) 。
第 (n+3) 至第 (n+q+2) 行每行若干个正整数，其中前三个数为 (z_i,t_i,s_i)，之后为 (2 imes s_i) 个正整数，表示每个区间的左右端点。
各变量具体含义见题目描述所述。
输出格式
对于 (zP1nG) 进行的每次尝试，输出一行一个数表示从 (zP1nG) 的位置到灭霸的位置所需的最短时间，如果 (zP1nG) 无法到达灭霸的位置则输出 (-1) 。
样例
样例输入
6 2
1 2 4 1
2 1 3 3
3 1 2 2
4 3 4 5
5 2 4 3
6 1 4 2
4
1 4 1 1 3
1 4 1 1 4
1 4 2 5 5 2 3
1 4 1 1 6
样例输出
-1
8
5
2
数据范围与提示
对于 (100\%) 的数据，(1≤n≤100,000)，(1≤S≤5)，(1≤p_i≤2,000)，(u_i≠v_i)，(z_i≠t_i)，(1≤w_i≤100,000,000)，(1≤∑s_i≤10,000) 。
保证每次尝试的区间没有交集，各测试点的约定见下表。
(S) 的含义如下：
(1)：保证 (u_i,v_i≤1) 。
(2)：保证每个 (p_i) 各不相同。
(3)：保证 (∑s_i≤50) 。
(4)：保证每个询问区间的左端点 (=1) 。
(5)：无特殊限制。
注意：整数 (S) 只是为了让你更容易地完成子任务，你可能不会用到 (S) 。
思路
很独特的一个思路，我们发现整张图，只有 (9) 个点，这么少的节点，我们可以跑最短路中的 (Floyd)，但是优先级怎么处理呢？
我们可以想到矩阵乘法，不过我们这里不是加和，而是取 (min)，将同一优先级的最短路存在一个矩阵里。
然后我们可以建一个矩阵的线段树，从小到大存，查询时，注意计算不能够交换，因为矩阵乘不满足乘法交换律。
没啥可讲的，差不多就是线段树板子，将 (int) 换成 (Matrix) 。
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 2e3 + 50, INF = 0x3f3f3f3f3f3f3f3f;
inline int read(){
int x = 0, w = 1;
char ch;
for(; ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') w = -1;
for(; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
return x * w;
}
int n, S, Q;
struct Node{
int l, r;
}q[maxn];
bool cmp(Node x, Node y){
return x.l < y.l;
}
struct Matrix{
int a[10][10];
Matrix() {
memset(a, 0x3f, sizeof a);
for (int i = 1; i <= 9; i++) {
a[i][i] = 0;
}
}
Matrix operator * (const Matrix &b) const {
Matrix c;
for (int k = 1; k <= 9; k++)
for (int i = 1; i <= 9; i++)
for (int j = 1; j <= 9; j++)
c.a[i][j] = min(c.a[i][j], a[i][k] + b.a[k][j]);
return c;
}
}a[maxn],tree[maxn<<2];
void Floyd(){
for (int s = 1; s <= maxn; s++) {
for (int k = 1; k <= 9; k++) {
for (int i = 1; i <= 9; i++) {
for (int j = 1; j <= 9; j++) {
a[s].a[i][j] = min (a[s].a[i][j], a[s].a[i][k] + a[s].a[k][j]);
}
}
}
}
}
void Build(int rt, int l, int r){
if (l == r) {
tree[rt] = a[l];
return;
}
int mid = (l + r) >> 1;
Build(rt << 1, l, mid);
Build(rt << 1 | 1, mid + 1, r);
tree[rt] = tree[rt << 1] * tree[rt << 1 | 1];
}
Matrix Query(int rt, int l, int r, int s, int t){
if (l == s && r == t) {
return tree[rt];
}
int mid = (l + r) >> 1;
if (t <= mid) return Query(rt << 1, l, mid, s, t);
if (s > mid) return Query(rt << 1 | 1, mid + 1, r, s, t);
return Query(rt << 1, l, mid, s, mid) * Query(rt << 1 | 1, mid + 1, r, mid + 1 , t);
}
signed main(){
n = read(), S = read();
for (int i = 1; i <= n; i++) {
int p = read(), u = read(), v = read(), w = read();
a[p].a[u + 1][v + 1] = min(a[p].a[u + 1][v + 1], w);
}
Floyd();
Build(1, 1, maxn);
Q = read();
while (Q--) {
Matrix ans;
memset(q, 0, sizeof q);
int u = read(), v = read(), opt = read();
u++;
v++;
for (int i = 1; i <= opt; i++) {
q[i].l = read(), q[i].r = read();
}
sort(q + 1, q + 1 + opt, cmp);//区间排序
for (int i = 1; i <= opt; i++) {
ans = ans * Query(1, 1, maxn, q[i].l, q[i].r);
}
if (ans.a[u][v] == INF) {
printf("-1
");
}else {
printf("%lld
", ans.a[u][v]);
}
}
return 0;
}