手机网站开发语言,郑州市重点项目建设办公室网站,做网站的版权问题,做软件的公司网站有哪些文章目录1. 题目2. 解题1. 题目 来源#xff1a;https://tianchi.aliyun.com/oj/15165469968503404/76745683739284070
2. 解题
按道理可以DP暴力求解#xff0c;但是数据规模太大#xff0c;会超时的
手算前几项#xff0c;然后去 oesi 网站查询数列#xff0c;找到 大…
文章目录1. 题目2. 解题1. 题目 来源https://tianchi.aliyun.com/oj/15165469968503404/76745683739284070
2. 解题
按道理可以DP暴力求解但是数据规模太大会超时的
手算前几项然后去 oesi 网站查询数列找到 大施罗德数就是本题的答案 但是这个数列的递推公式是 FnFn−1∑k0n−1Fk∗Fn−1−kF_{n}F_{n-1}\sum_{k0}^{n-1} F_{k} * F_{n-1-k}FnFn−1k0∑n−1Fk∗Fn−1−k
是 O(n2)O(n^2)O(n2) 时间复杂度会超时
又查到 超级卡特兰数 Fn∗(n1)(6∗n−3)∗Fn−1−(n−2)∗Fn−2F_{n} *(n1)(6 * n-3) * F_{n-1}-(n-2) * F_{n-2}Fn∗(n1)(6∗n−3)∗Fn−1−(n−2)∗Fn−2 发现除了第 0 项以外超级卡特兰数 X 2 大施罗德数。厉害 另外超级卡特兰数要求 FnF_nFn 要除以 (n1)(n1)(n1)要用到除法的求模转换方法。 除法是无法直接求模的。有以下方法。
除法求模 快速幂
a / c mod pa / c mod p * 1a / c mod p * c^(p-1) mod pa * c^(p-2) mod p或者 乘法逆元法
inv[1] 1;
for (int i 2; i n; i)
{inv[i] (mod - mod/i) * inv[mod%i] % mod;//求模运算的乘法逆元
}解答
class Solution {vectorlong long catalan;int mod 1e97;
public:/*** param n: The number of pyramid levels n* param k: Possible coordinates k* return: Find the sum of the number of plans*/int pyramid(int n, vectorint k) {// write your code herelong long sum 0;catalan vectorlong long(n1, 0);catalan[0] 1;catalan[1] 1;vectorlong long inv(n1);inv[1] 1;for (int i 2; i n; i){inv[i] (mod - mod/i) * inv[mod%i] % mod;//求模运算的乘法逆元}for(int i 2; i n; i){catalan[i] ((catalan[i-1]*(6*i-3)%mod)-((i-2)*catalan[i-2]%mod)mod)*inv[i1]%mod;}for(int i 0; i k.size(); i){sum (sumcal(n,k[i]))%mod;}return sum;}long long cal(int n, int k){if(n k) return 1;return (catalan[n-k]*2)%mod;}
};我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
