Calebe Martines e sua equipe, a Relative Cinema, fará uma rifa valendo uma verdadeira fortuna, e todos estão concorrendo!
Sabemos que $$$n$$$ pessoas participarão da rifa, e Calebe fará $$$k$$$ sorteios. Seus amigos, John Pepper e Caô, estão preocupados com a possibilidade de pessoas ganharem mais de um sorteio. Para ajudá-los a analizar essas possibilidades, você deve calcular, para todo $$$i$$$ de $$$1$$$ até $$$k$$$, de quantas maneiras podemos fazer $$$k$$$ sorteios de forma que exatamente $$$i$$$ pessoas foram sorteadas pelo menos uma vez.
Como esse valor é muito grande, calcule-o módulo $$$998244353$$$. Ajude o Relative Cinema a fazer cinema!
A única linha de entrada contém dois inteiros $$$n$$$ e $$$k$$$ $$$(1 \leq k \leq 5000$$$; $$$1 \leq n \leq 10^9$$$; $$$k \leq n)$$$ — o número de pessoas e o número de escolhas feitas, repectivamente.
Imprima $$$k$$$ inteiros $$$r_1, \dots, r_k$$$ — os valores desejados módulo $$$998244353$$$.
4 2
4 12
1000000000 7
1755647 80864928 571635738 255555236 735398618 309020519 630212989
Arthur_9548 e MagePetrus, em sua empresa de jogos É Só Fazer®, estão criando um jogo chamado Kaskata, no qual o jogador deve jogar bolas para fazer pontos.
As regras do jogo funcionam da seguinte forma. Existem $$$n$$$ bumpers numerados de $$$1$$$ até $$$n$$$ de forma ordenada, e o jogador solta uma bola com $$$m$$$ de energia no bumper $$$x$$$. Quando a bola acerta o bumper $$$x$$$, se ela possuir energia positiva são criadas duas bolas, com $$$m-1$$$ de energia cada, que são lançadas em direção aos bumpers $$$(x-1)$$$ e $$$(x+1)$$$ (se estes existirem). Toda vez que uma bola acerta um bumper, a pontuação dele é aumentada em $$$1$$$.
Dudu foi chamado para testar o jogo. Ele lançará uma bola com $$$m$$$ de energia no bumper $$$x$$$. Ajude no debugging do jogo e encontre a pontuação final de cada bumper. Como esse valor pode ser muito grande, calcule-o módulo $$$998244353$$$.
A primeira linha de entrada contém três inteiros $$$n$$$, $$$x$$$ e $$$m$$$ ($$$1 \leq x \leq n \leq 100$$$; $$$0 \leq m \leq 10^9$$$) — a quantidade de bumpers, a posição inicial e a energia inicial da bola, respectivamente.
Imprima uma única linha com $$$n$$$ inteiros $$$p_1, \dots, p_n$$$ — a pontuação de cada um dos $$$n$$$ bumpers módulo $$$998244353$$$.
5 2 0
0 1 0 0 0
5 2 1
1 1 1 0 0
5 2 2
1 3 1 1 0
5 2 3
3 3 4 1 1
1 1 100000
1
Você recebe dois inteiros $$$n$$$ e $$$m$$$ com $$$1 \le m \le n$$$.
Considere uma tabela composta por duas linhas. A linha superior contém $$$n$$$ células, e a linha inferior contém $$$m$$$ células. As células de cada linha estão ordenadas da esquerda para a direita, e as colunas são formadas pelas células que ocupam a mesma posição a partir da esquerda (apenas para as posições de $$$1$$$ até $$$m$$$).
Você deve distribuir todos os inteiros de $$$1$$$ até $$$n+m$$$ nas células da tabela, usando cada inteiro exatamente uma vez, de modo que as seguintes condições sejam satisfeitas:
Sua tarefa é calcular o número de maneiras diferentes de preencher a tabela de forma válida. Como esse número pode ser muito grande, calcule-o módulo $$$998244353$$$.
Dois preenchimentos são considerados diferentes se existir ao menos uma célula que contenha números diferentes.
Abaixo, um possível preenchimento para $$$n=4$$$ e $$$m=3$$$.
A única linha de entrada contém dois inteiros $$$n$$$ e $$$m$$$ $$$(1 \leq n, m \leq 2 \cdot 10^5)$$$ — o comprimento da primeira e segunda linhas, respectivamente.
Imprima um único inteiro — o número de preenchimentos, módulo $$$998244353$$$.
3 2
5
4 2
9
12345 6789
447370075
O Mágico Enzo fará uma apresentação na UnB (Universidade de Baralhos), e para isso está treinando uma forma de embaralhar cartas chamado Embaralhamento Mágico.
Vamor denotar um baralho de $$$n$$$ cartas como um vetor $$$a$$$ de tamanho $$$n$$$. O embaralhamento funciona da seguinte forma: separamos os elementos de posições ímpares (indexado em $$$1$$$) no vetor $$$l$$$ e os elementos de posições pares no vetor $$$r$$$. Depois concatenamos $$$r$$$ em $$$l$$$ ($$$a = l + r$$$).
Um truque conhecido é embaralhar o baralho vezes o suficiente para que ele volte ao estado inicial. Ajude Enzo e calcule quantos Embaralhamentos Mágicos é necessário para que um baralho de $$$n$$$ cartas distintas volte ao seu estado inicial.
A única linha de entrada contém um inteiro par $$$n$$$ $$$(1 \leq n \leq 10^6)$$$, o tamanho do baralho.
Imprima um único inteiro positivo: a menor quantidade de Embaralhamentos Mágicos para que o baralho volte a seu estado inicial.
8
3
6
4
1000000
180
Vamos denotar as 8 cartas do baralho por $$$[1, 2, 3, 4, 5, 6, 7, 8]$$$. O embaralhamento leva este baralho ao vetor $$$[1, 3, 5, 7, 2, 4, 6, 8]$$$. A sequência inteira fica:
$$$[1, 2, 3, 4, 5, 6, 7, 8]$$$ ->
$$$[1, 3, 5, 7, 2, 4, 6, 8]$$$ ->
$$$[1, 5, 2, 6, 3, 7, 4, 8]$$$ ->
$$$[1, 2, 3, 4, 5, 6, 7, 8]$$$,
dando a resposta $$$3$$$.
Let $$$s$$$ be a string consisting of characters 'A', 'B' or 'C'. A regular partition of $$$s$$$ is a partition of $$$s$$$ in subsequences such that every subsequence is equal to one of the following:
A string $$$s$$$ is a regular ternary string if it has a regular partition.
Given an integer $$$n$$$ and a string $$$p$$$, count the number of regular ternary strings of size $$$n$$$ that has $$$P$$$ as its prefix. Since the number can be really big, output it modulo $$$998'244'353$$$.
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 200$$$) — the number of testcases.
The first line of each test case contains two integers $$$n$$$, $$$m$$$ ($$$1 \leq m \leq n \leq 200$$$) — the size of the strings we want to count and the size of the prefix, respectively.
The second line contains a string $$$p$$$ ($$$1 \leq |p| \leq n$$$; $$$p_i \in \{'A', 'B', 'C'\}$$$) — the prefix of the strings.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$200$$$.
Output a single integer — the number of regular ternary strings of size $$$n$$$ that has $$$p$$$ as its prefix, modulo $$$998'244'353$$$.
64 1A4 4ABAC4 4BCBC4 4CACB6 1A123 3ABC
12 1 1 0 90 0
For the first case with $$$n = 4$$$ and $$$p$$$ = A, the following strings are regular and has $$$p$$$ as its prefix:
Lucas Sala, campeão mundial de Karate, realizará um n-man kumite; um teste extremo de resistência física e mental, no qual deve-se lutar contra $$$n$$$ outros atletas. Mas para Lucas não basta vencer as lutas, ele também deve lutar com estilo e impressionar a audiência!
Cada um dos $$$i$$$ atletas participantes tem um valor de estilo $$$v[i]$$$, então Lucas ganhará $$$v[i]$$$ pontos de estilo ao derrotá-lo. Porém cada atleta tem um mestre $$$p[i]$$$ (que também está participando da luta!), que fica mais motivado quando seu aprendiz é derrotado, o que implica em mais pontos de estilo ao derrotar o mestre. Mais formalmente, se o atleta $$$i$$$ é derrotado então os pontos de estilo ao derrotar o mestre é aumentado em $$$v[i]$$$, isto é, $$$$$$v[p[i]] += v[i] \ .$$$$$$ Ajude Lucas e encontre o maior valor de estilo que ele pode obter ao realizar o n-man kumite.
A primeira linha de entrada contém um único inteiro $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — a quantidade de atletas no kumite.
A segunda linha de entrada contém $$$n$$$ inteiros $$$v_i$$$ ($$$1 \leq v_i \leq 10^9$$$), separados por um espaço em branco — o estilo inicial do $$$i$$$-ésimo atleta.
A terceira e última linha contém também $$$n$$$ inteiros $$$p_i$$$ ($$$1 \leq p_i \leq n$$$), separados por um espaço em branco — o mestre do $$$i$$$-ésimo atleta.
Imprima um único inteiro — o maior valor de estilo que pode ser adquirido por Lucas Sala.
5 2 5 4 2 3 2 3 1 1 1
40
5 1 2 3 2 1 2 3 4 5 1
31
3 1 2 3 1 1 1
11