[Original] Int ?
暂无测试数据。
Background
SQY在睡梦中惊醒。
望着黑漆漆的天花板,SQY失眠了。这时,远方飞来了一条曲线:
\[y=\sum ^n_{i=1} \sum ^m_{j=1} \sum ^{ij}_{k=1} a_k x^{i+j}\]
其飞过了SQY的头顶,洒下一片光辉,让SQY的电脑爆炸了。
为了修好SQY的电脑,需要了解这条抛物线在SQY家中洒下了多少光辉。你能帮帮SQY吗?
Description
给定上述抛物线\(y=f(x)\),求曲线与直线\[y=0, x=t, x=u\]构成的曲边梯形组成的面积
Format
Input
输入的第一行包含三个整数\(n, m, p\)。其中\(p\)的作用会在下文讲述。
接下来有\(n \times m\)行,每行一个整数\(a_i\)。
Output
输出一个实数\(r\),要求误差不超过\(2^{{(n+m)}} e^{-p^2\;sgn(p)}\),其中\(e=\lim\limits_{n\to\infty}\left(1+\frac{1}{n}\right)^n\),\(sgn(p)\)为\(p\)的正负号
Sample 1
Input
123 500
Output
623
Limitation
对于满足性质①的测试点,分配128 MB的内存和2.0 s的时限
对于满足性质②、③、④的测试点,分配256 MB的内存和6.0 s的时限
对于满足性质⑤的测试点,分配512 MB的内存和10.0 s的时限
(10%)对于满足性质①的测试点,\(n, m \leqslant 5\),\(|a_i|, p\leqslant 5\), \(t, u\leqslant 1000\)
(20%)对于满足性质②的测试点,\(n \leqslant 10^4, m\leqslant 5, |a_i| \leqslant 500,p \leqslant 30, t, u\leqslant 5000\)
(20%)对于满足性质③的测试点,\(n \leqslant 2\times10^4, m\leqslant 2\times10^4, |a_i| \leqslant 500, p \leqslant -\left(\frac{\pi}{e}\right)^2, t, u \leqslant 10^6\)
(20%)对于满足性质④的测试点,\(n \leqslant 10, m \leqslant 10, |a_i| \leqslant 50, p \leqslant 10^4, t,u\leqslant 10^6\)
(30%)对于满足性质⑤的测试点,\(n, m \leqslant 10^4, |a_i| \leqslant 10^4, p \leqslant 10^3, t,u \leqslant 10^6\)
Tips
对于前10%的测试点,你应该可以暴力通过
对于10% ~ 70%的测试点,你应该可以针对数据的特征,设计一个常数为\(1/4\),复杂度\(O(n^2m^2)\)的朴素算法或\(O\left(e^{p^2}(t-u)+n+m\right)\)的算法
对于70% ~ 100%的测试点,你应该可以设计一个\(O(knm)\)的算法。其中\(k \leqslant \max{n,m}\)
信息
- 难度
- (无)
- 分类
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 通过率
- ?
- 上传者