P5148 题解

BINYU · 2022-01-04 21:50:18 · 题解

思路

先把原式写成数学形式，即 \Sigma^{n}_{a_{1} = 1}\Sigma^{a_{1} - 1}_{a_{2} = 1} \Sigma^{a_{2} - 1}_{a_{3} = 1} ... \Sigma^{a_{k - 1} - 1}_{a_{k} = 1}f(q) 。

这里 f(q) 是可以直接求出的，不受 a_{1},a_{2},a_{3}...a_{k} 的影响，所以可以先提出来，再来看前面 k 个求和，可以发现 a_{1}<a_{2}<a_{3}<...<a_{k},所以 a 序列是有序的（递增），并且任意两个元素是不同的，那么题就转化成了在 1 至 n 中选 k 个不同的数，按从小到大排列，方案数是多少，再乘上系数 f(q) ,而选 k 个不同的数又不要求顺序不就是排列吗？那么前面的 k 个求和就是 C^{k}_ {n} = \frac{n!}{k!(n-k)!} 答案也就是 \frac{n!}{k!(n-k)!}f(q) 。

完了？

不，还没有

本体涉及到有理数取模，要求 k!(n-k)! , 或者只求一个（具体见代码），本人不习惯（bu hui）用扩展欧几里得算法求逆元,习惯（zhi hui）用线性求逆元，但因为有阶乘的存在，时间复杂度其实都是 O(k) 级。

坑点

2. 循环里的 a_{i} 不是读入的 a_{i} ，读入的 a_{i} 代表 f(q) 里的 a_{i} 。

3. 不要以为只有 q 需要开 long long ，所有的（ n,m,k,a_{i} 除外 ）都要开

代码

#include<bits/stdc++.h>//万能头
using namespace std;
#define ll long long
const int p = 1e9 + 7;
ll n,m,k,q,a[500005],ans,s = 1,inv[500005];//十年OI一场空，不开long long见祖宗
ll C(int x,int y)//组合
{
    ll w = 1;
    for(int i = x - y + 1;i <= x;i++)//从 (n - k + 1) 至 n 的积，把(n - k)!约掉了 
        w = (w * i) % p;
    for(int i = 1;i <= y;i++)
        w = (w * inv[i]) % p;//k!的逆元
    return w;
}
int main()
{
    cin>>n>>m>>k>>q;
    q %= p;
    inv[1] = 1;//初始化逆元
    for(ll i = 2;i <= n;i++)//线性求逆元
        inv[i] = (p - p / i) * inv[p % i] % p;
    for(int i = 0;i <= m;i++)
        cin>>a[i];
    for(int i = 0;i <= m;i++)
        ans = (ans + a[i] * s) % p,s = (s * q) % p;//f(q)
    cout<<ans * C(n,k) % p<<endl;//最后也要对p取模
}