Codeforces 102394I Interesting Permutation 思维
2024-10-11 05:27:44
题意:
你有一个长度为n的序列a(这个序列只能使用[1,n]区间内的数字,每个数字只能使用一次),通过a序列可以构造出来三个相同长度的序列f、g、h
- For each 1≤i≤n, fi=max{a1,a2,…,ai};
- For each 1≤i≤n, gi=min{a1,a2,…,ai};
- For each 1≤i≤n, hi=fi−gi.
问你,如果给你h序列,你要找出来满足h序列的a序列的个数。答案很大你可以取模于1e9+7
题解:
一、
首先先特判掉几种情况
1、如果h数组里面出现hi>n-1,那么直接输出0
2、如果h数组里面没有出现n-1,那么直接输出0
3、如果h数组是非严格递增序列就不特判,否则输出0
4、如果h0不等于0,直接输出0
二、
1、对于剩下的情况,如果hi>hi-1,那么hi这个位置上面不是前i个中的最大值就是最小值。有两种情况,所以结果乘于2
2、如果hi==hi-1,那么证明hi这个位置上的数字是[1,i-1]这个区间内的最大数字和最小数字之间的数字。我们假设这个区间内最大数字hi和最小数字hj之间的数字有num个还没有使用过,那么答案就可以乘于num
那么这个num怎么计算呢,其实对于hi>hi-1,它们的差值hi-h(i-1)-1就是在原num的基础上又新增加了hi-h(i-1)-1个最大值和最小值之间没使用过的中间数字
(以上hi-1代表下标为i-1的h数组中对应的值)
为什么hi-h(i-1)还要再减去1,是因为hi也占用了一个数字
代码:
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=1e5+10;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
typedef long long ll;
ll h[maxn];
int main()
{
ll t;
scanf("%lld",&t);
while(t--)
{
ll n,flag=0,flag1=0;
h[0]=0;
scanf("%lld",&n);
for(ll i=1;i<=n;++i)
{
scanf("%lld",&h[i]);
if(h[i]==n-1) flag1=1;
if(h[i]<h[i-1]) flag=1;
if(h[i]>n-1) flag=1;
}
if(h[1]!=0) flag=1;
if(flag || !flag1)
{
printf("0\n");
continue;
}
ll num=0,ans=1;
for(ll i=2;i<=n;++i)
{
if(h[i]>h[i-1]) ans=(ans<<1)%mod,num+=(h[i]-h[i-1]-1);
else
{
ans=(ans*num)%mod;
num--;
}
}
printf("%lld\n",ans);
}
return 0;
}
最新文章
- python基础知识(四)
- CloudStack系统部署系列教程-KVM
- netfx_NativeCompilation.msi 传说中的 .NET Native 预览版的文件列表
- Android_用户界面概述和数据单位
- Wireshark和TcpDump抓包分析心得
- 93. Restore IP Addresses
- Codeforces Burning Midnight Oil
- (6)Xamarin.android google map v2
- numpy之索引和切片
- jsp 九大内置对象和其作用详解
- 协议系列之IP协议
- centos安装图形界面
- 更改MySQL/Postgresql密码
- 【Spark调优】小表join大表数据倾斜解决方案
- [模板]Link-Cut-Tree动态树
- Writing DynamicTableEntity to Azure Storage Table
- 5月17 AJAX返回类型-------JSON和XML
- python scrapy 数据处理时间格式转换
- 阅读<;<;HDMI 1.4/2.0 Transmitter Subsystem V2.0>;>;笔记
- hadoop详细了解5个进程的作用