Short Colorful Strip
传送门
题面翻译
题目描述
这是F题的第一个子任务。F1和F2的区别仅在对于m和时间的限制上
有n+1种颜色标号从0到n，我们有一条全部染成颜色0的长为m的纸带。
Alice拿着刷子通过以下的过程来给纸带染色：
我们按照从1到n的顺序进行染色，进行每次染色时，我们选取一个区间[ai,bi]，0<=ai<bi<=m，并且这个区间内必定是单种颜色。
染色到最后，纸带上有各种颜色除了颜色0.给出纸带最终的状态，问有多少种不同的染色方案能到达最终状态。输出时结果模998244353。
输入格式
第一行有两个整数n和m，1<=n<=500，并且保证m=n。n代表除了颜色0有多少种颜色，m代表纸带的长度。
第二行有m个用空格分隔的整数c1,c2,…,cm,(1<=ci<=n)，代表完成染色后纸带的最终状态。保证最终状态中能在纸带上找到从1到n所有的颜色。
注意，这个子任务保证了n=m，那么就是说最终状态是1到n的一个排列。
输出格式
输入一个单独的整数，即Alice可行的染色方案数模998244353.
题目描述
This is the first subtask of problem F. The only differences between this and the second subtask are the constraints on the value of m m m and the time limit. You need to solve both subtasks in order to hack this one.
There are n + 1 n+1 n+1 distinct colours in the universe, numbered 0 0 0 through n n n . There is a strip of paper m m m centimetres long initially painted with colour 0 0 0 .
Alice took a brush and painted the strip using the following process. For each i i i from 1 1 1 to n n n , in this order, she picks two integers 0 ≤ a i < b i ≤ m 0 \leq a_i < b_i \leq m 0≤ai<bi≤m , such that the segment [ a i , b i ] [a_i, b_i] [ai,bi] is currently painted with a single colour, and repaints it with colour i i i .
Alice chose the segments in such a way that each centimetre is now painted in some colour other than 0 0 0 . Formally, the segment [ i − 1 , i ] [i-1, i] [i−1,i] is painted with colour c i c_i ci ( c i ≠ 0 c_i \neq 0 ci=0 ). Every colour other than 0 0 0 is visible on the strip.
Count the number of different pairs of sequences { a i } i = 1 n \{a_i\}_{i=1}^n {ai}i=1n , { b i } i = 1 n \{b_i\}_{i=1}^n {bi}i=1n that result in this configuration.
Since this number may be large, output it modulo 998244353 998244353 998244353 .
输入格式
The first line contains a two integers n n n , m m m ( 1 ≤ n ≤ 500 1 \leq n \leq 500 1≤n≤500 , n = m n = m n=m ) — the number of colours excluding the colour $ 0 $ and the length of the paper, respectively.
The second line contains m m m space separated integers c 1 , c 2 , … , c m c_1, c_2, \ldots, c_m c1,c2,…,cm ( 1 ≤ c i ≤ n 1 \leq c_i \leq n 1≤ci≤n ) — the colour visible on the segment [ i − 1 , i ] [i-1, i] [i−1,i] after the process ends. It is guaranteed that for all j j j between 1 1 1 and n n n there is an index k k k such that c k = j c_k = j ck=j .
Note that since in this subtask n = m n = m n=m , this means that c c c is a permutation of integers 1 1 1 through n n n .
输出格式
Output a single integer — the number of ways Alice can perform the painting, modulo $ 998244353 $ .
样例 #1
样例输入 #1
3 3
1 2 3
样例输出 #1
5
样例 #2
样例输入 #2
7 7
4 5 1 6 2 3 7
样例输出 #2
165
提示
In the first example, there are 5 5 5 ways, all depicted in the figure below. Here, 0 0 0 is white, 1 1 1 is red, 2 2 2 is green and 3 3 3 is blue.
Below is an example of a painting process that is not valid, as in the second step the segment 1 3 is not single colour, and thus may not be repainted with colour 2 2 2 .
解题思路
有题目描述可知， n = m n=m n=m，所以每个颜色只能涂一次。又可知，颜色要从编号小的到编号大的涂，所以可以用搜索算法，每次找出带子上颜色编号最小的位置作为基准点，算出 d f s ( l , m i n i d − 1 ) dfs(l,minid-1) dfs(l,minid−1)与 d f s ( m i n i d + 1 , r ) dfs(minid+1,r) dfs(minid+1,r)。而题目要求求涂色方案数，所以可以用乘法原理，算出 d f s ( l , m i n i d − 1 ) = d f s ( l , x − 1 ) × d f s ( x , m i n i d − 1 ) dfs(l,minid-1)=dfs(l,x-1) \times dfs(x,minid-1) dfs(l,minid−1)=dfs(l,x−1)×dfs(x,minid−1)、 d f s ( m i d i d + 1 , r ) = d f s ( m i n i d , x ) × d f s ( x + 1 , r ) dfs(midid+1,r)=dfs(minid,x) \times dfs(x+1,r) dfs(midid+1,r)=dfs(minid,x)×dfs(x+1,r)，因而 d f s ( l , r ) = d f s ( l , m i n i d − 1 ) × d f s ( m i d i d + 1 , r ) = d f s ( m i n i d , x ) × d f s ( x + 1 , r ) dfs(l,r)=dfs(l,minid-1) \times dfs(midid+1,r)=dfs(minid,x) \times dfs(x+1,r) dfs(l,r)=dfs(l,minid−1)×dfs(midid+1,r)=dfs(minid,x)×dfs(x+1,r)。
为了避免做重复涂色操作，所以要记忆化，用
t
o
n
g
l
,
r
tong_{l,r}
tongl,r
记录
l
l
l~
r
r
r 区间的涂色方案数。文章来源：https://www.toymoban.com/news/detail-790489.html
AC Code
// C++ includes used for precompiling -*- C++ -*-
// Copyright (C) 2003-2013 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 3, or (at your option)
// any later version.
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.
// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
// <Licenses - GNU Project - Free Software Foundation>.
/** @file stdc++.h
* This is an implementation file for a precompiled header.
*/
// 17.4.1.2 Headers
// C
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdalign>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif
// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
using namespace std;
#define int long long
const int Mod = 998244353;
const int Maxn = 500 + 5;
int n, m, a[Maxn];
int tong[Maxn][Maxn];//区块l~r的方案数
inline int dfs(int l, int r) {
if (tong[l][r]) {
return tong[l][r];
} else if (l >= r) {
tong[l][r] = 1;
} else {
int minid = l, tmp1 = 0, tmp2 = 0;
for (int i = l; i <= r; i++) {//求当前区块编号最小颜色
if (a[i] < a[minid]) {
minid = i;
}
}
for (int i = l; i <= minid; i++) {
tmp1 = (tmp1 + dfs(l, i - 1) * dfs(i, minid - 1) % Mod) % Mod;
}
for (int i = minid; i <= r; i++) {
tmp2 = (tmp2 + dfs(minid + 1, i) * dfs(i + 1, r) % Mod) % Mod;
}
tong[l][r] = tmp1 * tmp2 % Mod;
}
return tong[l][r];
}
inline void work() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
dfs(1, m);
cout << tong[1][m] % Mod << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
work();
return 0;
}
没看懂？戳我文章来源地址https://www.toymoban.com/news/detail-790489.html
到了这里，关于CF1178F1 Short Colorful Strip 题解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
