网站建设的博客,plc编程入门基础知识,编程网站网址,什么软件做网站好些[HNOI2013]数列
problem
洛谷链接
solution
假设每天的股价为 a[i]a[i]a[i]。则需满足 ∀ika[i1]−a[i]≤m\forall_{ik}a[i1]-a[i]\le m∀ika[i1]−a[i]≤m。又有参数满足 m(k−1)nm(k-1)nm(k−1)n。
也就是说每天的股价都可以取到上限#xf…[HNOI2013]数列
problem
洛谷链接
solution
假设每天的股价为 a[i]a[i]a[i]。则需满足 ∀ika[i1]−a[i]≤m\forall_{ik}a[i1]-a[i]\le m∀ika[i1]−a[i]≤m。又有参数满足 m(k−1)nm(k-1)nm(k−1)n。
也就是说每天的股价都可以取到上限即 ∀ika[i1]−a[i]m\forall_{ik}a[i1]-a[i]m∀ika[i1]−a[i]m。
当然都要保证 a[k]≤na[k]\le na[k]≤n。
这种每天都有增长求方案数的题目容易联想到差分。因为当差分数组确定时就只与第一个元素的值有关了。
用差分刻画数组 是很经典的套路。
令 ∀iks[i]a[i1]−a[i]\forall_{ik}s[i]a[i1]-a[i]∀iks[i]a[i1]−a[i]。
一个差分数组贡献都是 111。但是有若干种股价方案的差分数组是同一个就可以合并计算。
这里可以采用对第一天股价的起始值刻画出差分的增值一样但本质不同的股价方案。
显然方案数为 n−∑i1k−1s[i]n-\sum_{i1}^{k-1}s[i]n−∑i1k−1s[i]。因为在 a[1]∈[1,n−∑i1k−1s[i]]a[1]\in[1,n-\sum_{i1}^{k-1}s[i]]a[1]∈[1,n−∑i1k−1s[i]] 的时候都有 a[k]≤na[k]\le na[k]≤n。
而本质不同的差分数列的个数又为 mk−1m^{k-1}mk−1前面说过任何一天的增值都有可能取到 mmm。
综上可以得出答案的式子∑j1mk−1(n−∑i1k−1sj[i])nmk−1−∑j1mk−1∑i1k−1sj[i]\sum_{j1}^{m^{k-1}}(n-\sum_{i1}^{k-1}s_j[i])nm^{k-1}-\sum_{j1}^{m^{k-1}}\sum_{i1}^{k-1}s_j[i]∑j1mk−1(n−∑i1k−1sj[i])nmk−1−∑j1mk−1∑i1k−1sj[i]。
显然 sss 是将所有可能的合法差分数列都计算到了。并且有 sj[i]∈[1,m]s_j[i]\in[1,m]sj[i]∈[1,m]。
先不管差分数值那么后面一共就会有 mk−1(k−1)m^{k-1}(k-1)mk−1(k−1) 个数并且在 [1,m][1,m][1,m] 是均匀分布。
所以 [1,m][1,m][1,m] 中的每个数出现次数都是一样的即 mk−2(k−1)m^{k-2}(k-1)mk−2(k−1)。在乘上数值即可。
ansnmk−1−∑j1mk−1∑i1k−1sj[i]nmk−1−∑i1mi∗mk−2(k−1)ansnm^{k-1}-\sum_{j1}^{m^{k-1}}\sum_{i1}^{k-1}s_j[i]nm^{k-1}-\sum_{i1}^mi*m^{k-2}(k-1)ansnmk−1−∑j1mk−1∑i1k−1sj[i]nmk−1−∑i1mi∗mk−2(k−1)。
后面的式子就是个等差数列求和而已。
最后化简答案ansnmk−1−(m1)m2mk−2(k−1)ansnm^{k-1}-\frac{(m1)m}{2}m^{k-2}(k-1)ansnmk−1−2(m1)mmk−2(k−1)。
有的题解觉得这个除法有点坑有的用了 exgcd 求解逆元。
根本没有这种必要啊
逆元是因为不能整除所以才在 ppp 域内去找有相同效果的数。
但是明显 m(m1)m(m1)m(m1) 一定有一个是偶数一定能被 222 整除。
code
#include bits/stdc.h
using namespace std;
#define int long long
int n, m, k, p;int qkpow( int x, int y ) {int ans 1;while( y ) {if( y 1 ) ans ans * x % p;x x * x % p;y 1;}return ans;
}signed main() {scanf( %lld %lld %lld %lld, n, k, m, p );printf( %lld\n, ( n % p * qkpow(m, k - 1) % p - qkpow(m, k - 2) * (k - 1) % p * (m * (m 1) / 2 % p) % p p ) % p );return 0;
}
