String Counting
Contest: Educational Codeforces Round 104 (Rated for Div. 2)
Difficulty rating: 2700
Tags: combinatorics, dp, fft, math

You have $$$c_1$$$ letters 'a', $$$c_2$$$ letters 'b', ..., $$$c_{26}$$$ letters 'z'. You want to build a beautiful string of length $$$n$$$ from them (obviously, you cannot use the $$$i$$$-th letter more than $$$c_i$$$ times). Each $$$c_i$$$ is greater than $$$\frac{n}{3}$$$.

A string is called beautiful if there are no palindromic contiguous substrings of odd length greater than $$$1$$$ in it. For example, the string "abacaba" is not beautiful, it has several palindromic substrings of odd length greater than $$$1$$$ (for example, "aca"). Another example: the string "abcaa" is beautiful.

Calculate the number of different strings you can build, and print the answer modulo $$$998244353$$$.

Input format:
The first line contains one integer $$$n$$$ ($$$3 \le n \le 400$$$).

The second line contains $$$26$$$ integers $$$c_1$$$, $$$c_2$$$, ..., $$$c_{26}$$$ ($$$\frac{n}{3} < c_i \le n$$$).

Output format:
Print one integer — the number of strings you can build, taken modulo $$$998244353$$$.

Constraints:
Time limit: 10.0 s
Memory limit: 1024.0 MB

Example input:
4
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

Example output:
422500

Example input:
3
2 2 2 2 2 2 3 3 3 2 2 2 2 2 2 3 3 3 2 2 3 2 2 3 2 2

Example output:
16900

Editorial:
Suppose there is no constraint on the number of letters used. Then this problem can be solved with the following dynamic programming: let $$$dp_{i, j, k}$$$ be the number of strings of length $$$i$$$ ending with characters $$$j$$$ and $$$k$$$ that don't contain palindromes of odd length greater than $$$1$$$ (obviously, each forbidden palindrome contains a subpalindrome of length $$$3$$$, so we only need to ensure that there are no palindromes of length $$$3$$$).
The thing we are going to use in order to ensure that all the constraints on the number of characters are met is inclusion-exclusion. Since each $$$c_i > \frac{n}{3}$$$, at most two characters can violate their constraints in a single string, so we will iterate on some character of the alphabet and subtract the number of strings violating the constraint on this character from the answer, then iterate on a pair of characters and add the number of strings violating the constraints on these two characters to the answer.
Okay, how to calculate the number of strings violating the constraint on some fixed character? Let's use dynamic programming $$$f_{i, j, k, l}$$$ — the number of strings such that they contain $$$i$$$ characters, $$$j$$$ of them have the same type that we fixed, the previous-to-last character is $$$k$$$ and the last character is $$$l$$$. The number of states here seems to be something about $$$n^2 \cdot 26^2$$$, but in fact, $$$k$$$ and $$$l$$$ can be optimized to have only two different values since we are interested in two types of characters: the ones that coincide with the character we fixed, and the ones that don't.
Okay, what about violating the constraints on two characters? The same method can be used here: let $$$g_{i, j, k, l, m}$$$ be the number of strings consisting of $$$i$$$ characters such that the number of occurrences of the first fixed character is $$$j$$$, the number of occurrences of the second fixed character is $$$k$$$, the previous-to-last character is $$$l$$$ and the last character is $$$m$$$. Again, at first it seems that there are up to $$$n^3 \cdot 26^2$$$ states, but $$$l$$$ and $$$m$$$ can be optimized to have only $$$3$$$ different values, so the number of states is actually $$$n^3 \cdot 3^2$$$.
It seems that we have to run this dynamic programming for each pair of characters, right? In fact, no, it is the same for every pair of characters, the only difference is which states violate the constraints and which don't. We can run this dp only once, and when we need an answer for the pair of characters $$$(x, y)$$$, we can use two-dimensional prefix sums to query the sum over $$$g_{i, j, k, l, m}$$$ with $$$i = n$$$, $$$j > c_x$$$ and $$$k > c_y$$$ in $$$O(1)$$$. In fact, this dynamic programming can also be used for the first and the second part of the solution (calculating the strings that don't violate any constraints and the strings that violate the constraints on one character), so the hardest part of the solution runs in $$$O(n^3)$$$, though with a pretty big constant factor.