GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

Tuesday 28 June 2022

[Solution] PermutationForces II Codeforces Solution


E. PermutationForces II
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a permutation a of length n. Recall that permutation is an array consisting of n distinct integers from 1 to n in arbitrary order.

You have a strength of s and perform n moves on the permutation a. The i-th move consists of the following:

  • Pick two integers x and y such that ixymin(i+s,n), and swap the positions of the integers x and y in the permutation a. Note that you can select x=y in the operation, in which case no swap will occur.

You want to turn a into another permutation b after n moves. However, some elements of b are missing and are replaced with 1 instead. Count the number of ways to replace each 1 in b with some integer from 1 to n so that b is a permutation and it is possible to turn a into b with a strength of s.

Solution Click Below:-  👉CLICK HERE👈
👇👇👇👇👇

Since the answer can be large, output it modulo 998244353.

Input

The input consists of multiple test cases. The first line contains an integer t (1t1000) — the number of test cases. The description of the test cases follows.








The first line of each test case contains two integers n and s (1n21051sn) — the size of the permutation and your strength, respectively.

The second line of each test case contains n integers a1,a2,,an (1ain) — the elements of a. All elements of a are distinct.

The third line of each test case contains n integers b1,b2,,bn (1bin or bi=1) — the elements of b. All elements of b that are not equal to 1 are distinct.

It is guaranteed that the sum of n over all test cases does not exceed 2105.

Output

For each test case, output a single integer — the number of ways to fill up the permutation b so that it is possible to turn a into b using a strength of s, modulo 998244353.

No comments:

Post a Comment