{"problem":{"name":"01 Abs Sum","description":{"content":"You are given a sequence $A = (A_1, A_2, \\cdots, A_N)$ of length $N$, consisting of $0$, $1$, and $-1$. There are $2^q$ ways to replace all $-1$s in $A$ with either $0$ or $1$, where $q$ is the number","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":8000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"ttpc2024_2_k"},"statements":[{"statement_type":"Markdown","content":"You are given a sequence $A = (A_1, A_2, \\cdots, A_N)$ of length $N$, consisting of $0$, $1$, and $-1$.\nThere are $2^q$ ways to replace all $-1$s in $A$ with either $0$ or $1$, where $q$ is the number of $-1$s in $A$. Among these, for all sequences that contain both $0$ and $1$, calculate the sum of the answers to the following problem modulo $998244353$:\n\n> Let $\\alpha$ and $\\beta$ be the number of $0$s and $1$s in $A$, respectively.  \n> Also, let $X = (X_0, X_1, \\cdots, X_{\\alpha-1})$ be the sequence of indices of $A_i = 0$, arranged in increasing order, and let $Y = (Y_0, Y_1, \\cdots, Y_{\\beta-1})$ be the sequence of indices of $A_i = 1$, arranged in increasing order (note that the indices of $X$ and $Y$ start from $0$).  \n> \n> $\\displaystyle\\sum_{i=0}^{\\mathrm{LCM}(\\alpha, \\beta)-1} |X_{(i \\bmod \\alpha)} - Y_{(i \\bmod \\beta)}|$\n> \n> Calculate the value of the above expression.\n\nHere, $\\mathrm{LCM}(x, y)$ represents the least common multiple of $x$ and $y$, and $x \\bmod y$ denotes the remainder when $x$ is divided by $y$.\n\n## Constraints\n\n*   All input values are integers.\n*   $2 \\leq N \\leq 2250$\n*   Each $A_i$ is either $0$, $1$, or $-1$ $(i = 1, 2, \\cdots, N)$.\n\n## Input\n\nThe input is given in the following format:\n\n$N$\n$A_1$ $A_2$ $\\cdots$ $A_N$\n\n## Partial Score\n\n*   $30$ points will be awarded for passing the test set satisfying the additional constraint $N \\leq 100$.\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"ttpc2024_2_k","tags":[],"sample_group":[["4\n1 1 -1 -1","14\n\nFor $A = (1, 1, 0, 0)$, $|3 - 1| + |4 - 2| = 4$.  \nFor $A = (1, 1, 0, 1)$, $|3 - 1| + |3 - 2| + |3 - 4| = 4$.  \nFor $A = (1, 1, 1, 0)$, $|4 - 1| + |4 - 2| + |4 - 3| = 6$.  \nThus, the answer is $4 + 4 + 6 = 14$."],["3\n0 0 0","0\n\nSince it is not possible to form a sequence containing both $0$ and $1$, the answer is $0$."],["10\n-1 -1 0 -1 -1 1 -1 -1 -1 -1","10152"]],"created_at":"2026-03-03 11:01:14"}}