这题好没意思啊，怀疑拉不开区分度。

 

题意：求一个递增序列，每两个相邻数字之间的差值不超过m，最后一个值不能大于n。

 

分析：网上好多人用了差分，我没想到。然后YY了一发生成函数。

考虑构造生成函数G(x) = x+x2+…+xm.

我们的目标是求这个G(k-1)(x)的很多个前缀和。

具体来说是求什么呢？

这题的重点其实在于一个注意不到的细节：(k-1)*m<n。

这意味着，当第一项为1时，所有的答案一定被满足。

也就是说，当第一项为1时，对应的答案是G(k-1)(x)的所有项数之和。

实际上通过举例子，你会发现这样一个性质：[xi+k-1]G(k-1)(x) = [x(k-1)*m-i]G(k-1)(x) 其中i的范围自己想一下。

这个性质怎么证明呢：归纳

考虑将Gi(x)除以xi，然后乘以G(x)/x，然后把除的东西乘上。由于上一个具有这样的对称性，画图之后我们发现乘的时候是对称的，那么这个性质仍然满足。

 

通过我们对高斯的了解，我们知道他10岁的时候想到了1加到100的方法，他非常聪明，而我们只能照葫芦画瓢。

什么意思呢，我们考虑第一项为i的时候，在某个位置的时候出现了第一个不满足的序列。

然后从后往前，在某个位置出现了第一个满足的序列。

把两个匹配在一起，这样子我们得到了一个完整的序列，即(m)^(k-1).

 

众所周知，高斯是个很聪明的孩子,那么他用的方法很可能是将1到100翻倍然后两两配对，最后除以2。这个方法在这不好用。

我们不容易确认2在这个模数下有逆。

 

取而代之的方法是用类似1配99，2配98的方法。考虑多了一项怎么办。

不难发现的是，多出来的一项一定是配出来的结果的一半，不说明了。

做这个答案的时候一定要先留下一个m，将这个m除以2再乘进去。

 

代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 typedef long long ll;
 5 
 6 ll n,k,m,mod;
 7 ll pw,maxx;
 8 
 9 ll fast_pow(int now,int p){
10     if(p == 0) return 1;
11     if(p == 1) return now;
12     ll z = fast_pow(now,p/2);
13     z *= z; z %= mod;
14     if(p & 1) z*=now,z%=mod;
15     return z;
16 }
17     
18 int main(){
19     scanf("%lld%lld%lld%lld",&n,&k,&m,&mod);
20     maxx = (k-1)*m;
21     if(k == 1){printf("%lld",n);return;}
22     pw = fast_pow(m,k-1);
23     ll fir = n-maxx+1; // diyige youxiaci de
24     ll lst = n-(k-1); // zuihouyige youxiacide
25     ll len = lst-fir+1,multi = len/2;
26     ll ans = ((multi+n-maxx)%mod)*pw; ans %= mod;
27     if(len & 1){
28         pw = fast_pow(m,k-2);
29         pw *= (m/2);pw %= mod;
30         ans += pw;ans %= mod;\
31     }
32     printf("%lld",ans);
33     return 0;
34 }

 

版权声明：本文为1-1-1-1原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/1-1-1-1/p/8604501.html