Original link: https://www.shuizilong.com/house/archives/atcoder-regular-contest-146/
portal
Problem E. Simple Speed
To count, ask how many sequences of integers are there that satisfy the following conditions:
1. Each number occurs exactly Ai.
2. The absolute value of the difference between adjacent positions is exactly 1.
Personally I think this dp is very elegant!
First do not consider condition 2, then it is the polynomial coefficient .
Considering condition 2, it seems that we can brute force dp…
dp[i][j] represents the first i bits and the number of solutions with j at the end,
But this is obviously not feasible. . Because we can’t keep track of how much each number currently has left. .
So the core is that we want to avoid discussing how much of each number is left in the current state. . . Is there a way?
The answer is yes! It is enough to advance layer by layer , that is, to divide the stages by the size of the numbers. . .
Then apparently only at first. .
1 1 1
On the next level, we’re going to insert the 2 into the space between the 1s. . . Consider two boundary cases. . .
A minimum of 2 2s are required. . . become. .
1 2 1 2 1
There seems to be a maximum of 4 2s. . . become. .
2 1 2 1 2 1 2
Actually more than that. . Because we can continue to add 2 arbitrarily to both sides.
It’s just that the middle {2 1 2 1 2 1 2} is now a whole, and it is now equivalent to a {1} from the previous round. . . In this way we seem to have found a state that can be described. . sequence of sequences. .
For example if we have 6 2s, then this round we can be. .
{2} {2 1 2 1 2 1 2} {2}
{2 1 2 1 2 1 2} {2} {2}
{2} {2} {2 1 2 1 2 1 2} …
These three cases are equivalent to {1} {1} {1} in the first round. . .
So the task of each layer is to connect the gaps between these subsequences and generate some new gaps.
Or simpler to understand. . . The next round is finally equivalent to some {3} {3} {3} . . . Then we use the sequence of the previous layer to connect the sequence of this layer. . . A simple combination of numbers will do. .
The only state of the two sides that requires special discussion, because the two sides may be in a non-splicable state. .
So the state is dp[i][j][k]. . The current stage is i, the two sides can be spliced j times, and there are k positions in the middle that can be spliced. . The difficulty of transfer is still to discuss j.
. . .
Analyzing the state transition, we will find that this state space is very sparse, just open a map and run dp.
#include <lastweapon/number> using namespace lastweapon; const int N = int(2e5) + 5; int A[N]; Int F[N]; map<int, Int> dp[N][3]; int n; inline Int C(int n, int m){ return F[n]/(F[m]*F[nm]); } int main(){ #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); #endif MOD = 998244353; F[0] = 1; FOR(i, 1, N) F[i] = F[i - 1] * i; RD(n); REP(i, n) RD(A[i]); dp[0][2][A[0]-1] = 1; FOR(i, 1, n) REP(a, 3) for(auto it: dp[i-1][a]){ int x = it.fi; Int u = it.se; FOR_1(b, max(0, 1-x), min(a, A[i]-x)) { int y = A[i]-xb; dp[i][b][y] += u * C(A[i]-1, y) * C(a, b); } } Int z = 0; REP(i, 3) z += dp[n-1][i][0]; OT(z); }
This article is reprinted from: https://www.shuizilong.com/house/archives/atcoder-regular-contest-146/
This site is for inclusion only, and the copyright belongs to the original author.