当前位置:网站首页>Cf:c. the third problem
Cf:c. the third problem
2022-07-06 00:44:00 【White speed Dragon King's review】
analysis
This is a permutation problem
It looks fancy
Speaking of arrangement , We are going to find this arrangement 0 To n Corresponding subscript position
We have MET The definition is the smallest number except string , All strings must meet the same minimum number
therefore , We followed “ Minimum ”, From the smallest 0 Start to find the corresponding indexes one by one
First 0 I'm sure I can't change my position , secondly 1 Can't change ( Otherwise, we can always find an interval to make MET Unequal )
And then look 2 The number behind , use lr Maintain the left and right of the current index interval , And then if 2 stay lr In the words of , It has r - l + 1 - 2 A choice
If it is in the index range lr Outside , Then there must be a choice of interval that makes MET Unequal , For a better image , for instance :
+++2+++1+++0+(1)
++2++++1+++0+(2)
----+++++++++++
If we choose a line + The range of , That's obvious MET(1) > 2 and MET(2) = 2
So when we choose number k When we count , the previous lr The length of the index interval is r - l + 1
We have to id[i] It can be similar only in the index interval , At this time, the number of positions it can choose is r - l + 1 - i
use ans Just ride in tandem
ac code
import sys
input = sys.stdin.readline
MOD = 10 ** 9 + 7
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
id = [0] * n
for i, v in enumerate(a):
id[v] = i
# we judge from v = 0,1,...
ans = 1
l = r = id[0]
for i in range(1, n):
# if id[i] outside [l, r], no other choice
# cause there must be a choice MET not equal
if id[i] < l or id[i] > r:
l, r = min(id[i], l), max(id[i], r)
else:
ans = ans * (r - l + 1 - i) % MOD
print(ans)
summary
array + Sort + Internal and external simulation
Guess a reasonable situation by excluding some situations
边栏推荐
- Spark AQE
- [groovy] compile time metaprogramming (compile time method injection | method injection using buildfromspec, buildfromstring, buildfromcode)
- anconda下载+添加清华+tensorflow 安装+No module named ‘tensorflow‘+KernelRestarter: restart failed,内核重启失败
- 孤勇者
- Idea远程提交spark任务到yarn集群
- Leetcode Fibonacci sequence
- 【线上小工具】开发过程中会用到的线上小工具合集
- Illustrated network: the principle behind TCP three-time handshake, why can't two-time handshake?
- Codeforces gr19 D (think more about why the first-hand value range is 100, JLS yyds)
- 可恢复保险丝特性测试
猜你喜欢
Illustrated network: the principle behind TCP three-time handshake, why can't two-time handshake?
SAP Spartacus home 页面读取 product 数据的请求的 population 逻辑
Comment faire votre propre robot
KDD 2022 | EEG AI helps diagnose epilepsy
Analysis of the combination of small program technology advantages and industrial Internet
Atcoder beginer contest 258 [competition record]
Ffmpeg captures RTSP images for image analysis
电机的简介
I'm interested in watching Tiktok live beyond concert
Go learning - dependency injection
随机推荐
SAP Spartacus home 页面读取 product 数据的请求的 population 逻辑
devkit入门
数据分析思维分析方法和业务知识——分析方法(三)
Room cannot create an SQLite connection to verify the queries
OpenCV经典100题
curlpost-php
MIT doctoral thesis | robust and reliable intelligent system using neural symbol learning
[Chongqing Guangdong education] reference materials for Zhengzhou Vocational College of finance, taxation and finance to play around the E-era
Location based mobile terminal network video exploration app system documents + foreign language translation and original text + guidance records (8 weeks) + PPT + review + project source code
Natural language processing (NLP) - third party Library (Toolkit):allenlp [library for building various NLP models; based on pytorch]
curlpost-php
数据分析思维分析方法和业务知识——分析方法(二)
RAID disk redundancy queue
Go learning --- read INI file
XML Configuration File
LeetCode 1598. Folder operation log collector
Data analysis thinking analysis methods and business knowledge -- analysis methods (II)
如何利用Flutter框架开发运行小程序
[groovy] JSON serialization (jsonbuilder builder | generates JSON string with root node name | generates JSON string without root node name)
Common API classes and exception systems