自动搬运

查看原文

来自洛谷，原作者为

	龙·海流 我很懒，什么也没有留下

搬运于2025-08-24 22:07:39，当前版本为作者最后更新于2019-06-16 09:42:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

观察代码部分可以发现ans=循环次数*f(q)

处理循环次数：

1.显然的一点是a[1]>a[2]>...>a[k],即从a[1]到a[k]严格单减，因为a[k]最小为1，所以a[1]最小为k，最大为n；

2.开始递推：

先举个例子，设n=7，k=4；

a1=4时，a2~a4分别为3,2,1；

a1=5时，a1~a4可能为,{4,3,2}，{4,3,1}，{4,2,1}，{3,2,1}，即从4,3,2,1中扔掉一个数，剩下的三个数即为a2~a4，方案数为C(4,1);

a1=6时，从5,4,3,2,1中选出两个数扔掉，剩下三个数即为a2~a4，方案数为C(5,2);

a1=7时，从6,5,4,3,2,1中选出三个数扔掉，剩下三个数即为a2~a4，方案数为C(6,3);

于是a1=4时的方案数可看做C(3,0);

所以方案数=C(3,0)+C(4,1)+C(5,2)+C(6,3)=C(7,4);

（以下是计算过程：

ans=C(3,0)+C(4,1)+C(5,2)+C(6,3)=C(4,0)+C(4,1)+C(5,2)+C(6,3)=C(5,1)+C(5,2)+C(6,3)=C(6,2)+C(6,3)=C(7,3)=C(7,4)

应用性质：C(n+1,m)=C(n,m)+C(n,m-1);)

所以对于给定的n与k： a1=k时，方案数C(k-1,0);

a1=k+1时，方案数C(k,1);

a1=k+2时，方案数C(k+1,2);

a1=k+3时，方案数C(k+2,3);

......

a1=n时，方案数为C(n-1,n-k);

(为啥这里是C（n-1，n-k），一共有n-1个元素，需要留下k-1个，所以需要扔掉（n-1）-（k-1）个元素，即扔掉n-k个元素）

所以方案总数=C(k-1,0)+C(k,1)+C(k+1,2)+...+C(n-1,n-k)=C(n,n-k)=C(n,k)；

C(n,k)用阶乘求即可，卢卡斯在这里基本没用，因为n和k都小于1e9+7；当然，不要忘了求逆元；

然后就剩下f（q）了

暴力算乘方即使是快速幂都会很慢，但是这个式子可以通过提公因式转化一下；

还是先举个栗子：

f(q)=a3·x^3+a2·x^2+a1·x+a0
    =(a3·x^2+a2·x+a1)·x+a0
    =[(a3·x+a2)·x+a1]·x+a0

其实这个就是著名的秦九韶（shao2）算法，代码实现在下文中会给出；

最后附上自己的代码

	#include<iostream>
	#include<cstdio>
	#define ll long long
	using namespace std;
	const long long mod=1000000007;
	long long n,m,k,q,a[500010],ans;
	ll ksm(ll a,ll b)
	{	
    	    ll ret=1;
            while(b)
	    {
	        if(b&1) ret=ret*a%mod;
	        b>>=1;
	        a=a*a%mod;
	    }
	    return ret;
	}
	ll C()
	{
	    ll a=1,b=1;
	    for(ll i=n;i>=n-k+1;--i) a=a*i%mod;
	    for(ll i=2;i<=k;++i) b=b*i%mod;
	    return a*ksm(b,mod-2)%mod;
            //根据费马小定理，若a与p互质，那么a%p的逆元就是a^p-2，所以用快速幂求a%p的逆元
	}
	int main()
	{
	    scanf("%lld%lld%lld%lld",&n,&m,&k,&q);
	    q=q%mod;//不加这一句会少20分，很玄学
	    for(int i=0;i<=m;++i) scanf("%lld",&a[i]);
	    //秦九韶算法
	    for(ll i=m;i>0;--i) ans=(ans+a[i])*q%mod;
	    ans=(ans+a[0])%mod;//别忘了加上a0
	    ans=ans*C()%mod;
	    printf("%lld",ans);
	    return 0;
	}

组合数见高中数学选修3-3

秦九韶算法见高中数学必修3