2876: 云梯
内存限制:128 MB
时间限制:2.000 S
评测方式:文本比较
命题人:
提交:14
解决:3
题目描述
更好的阅读体验,请在https://github.com/hyandfhz/pic-bed/blob/master/files/%E4%BA%91%E6%A2%AF.md查看。
unicornFairy开始了新的学期。学校换了一个新校长,随之而来的是周五放学的时间由晚上七点半延时到了晚上八点半。unicornFairy认为这很不公平,所以她准备抢先一步回家。晚饭后,unicornFairy来到了一处没有监控的围墙旁。
小马将援助unicornFairy逃出学紫。学校的校长办公室共有n块石砖,小马使用魔法将这些垫脚石按1−n的编号空投至unicornFairy的位置。规定每个垫脚石有一个特征值a[i],这块垫脚石的长度和a[i]成反比例。unicornFairy需要将它们组成云梯。可惜unicornFairy实在是太
现在请你帮助unicornFairy写一个程序,求出云梯的最大高度h,并且求出对应的特征值的序列 b[i]。由于这道题被大佬lzyqwq秒了,现在需要你求出所有组成高度为k的云梯的所有方案数。请注意,每块垫脚石都是不同的,意味着两种方案的云梯形状可能是相同的。方案数对1,000,000,007取模。(详见样例1)
第一行,一个正整数n,表示垫脚石的个数。
第二行,n个正整数a[i],表示每个垫脚石的特征值a[i]。
第一行,一个正整数h,表示云梯最大的高度。
第二行,共h个正整数b[i],表示unicornFairy放置垫脚石的方案。
第三行,一个正整数k,表示搭出高度为h的云梯的所有方案数。方案数对1,000,000,007取模。
6 13 3 3 2 4 19
3 3 4 19 3
1. 13 3 3 2 4 19 ^ ^ ^ 2. 13 3 3 2 4 19 ^ ^ ^ 3. 13 3 3 2 4 19 ^ ^ ^
10 7 2 4 4 9 9 1 0 5 2
3 2 4 9 6
50 33 38 39 27 6 41 16 5 39 49 10 37 24 30 19 32 32 30 27 29 12 43 42 20 27 42 11 30 35 7 16 23 18 40 21 17 26 34 4 10 48 44 46 24 33 24 2 45 50 46
11 6 16 24 27 29 30 35 40 44 46 50 45
- 对于数据点weak1~5,n≤20且a[i]≤50
- 对于数据点6~10,n≤100且a[i]≤10,000
- 对于数据点11~20,没有额外限制。
- 对于全部数据,保证n≤1,000,000并且a[i]≤1,000,000,000
inline int read() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0' && ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}