题解 P5148 【大循环】

· · 题解

观察代码部分可以发现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