[原创]北信科1011 K. paulzhou和方程 [组合数学+差分序列]【数学】

2017-06-06 12:41:52 Tabris_ 阅读数：603

博客爬取于2020-06-14 22:40:06
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/72877015

题目链接:http://acm.hdu.edu.cn/diy/contest_showproblem.php?cid=31989&pid=1011
———————————————————————————————————————————
K. paulzhou和方程

Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/102400K (Java/Other)
Total Submission(s) : 28 Accepted Submission(s) : 7
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
众所周知，paulzhou的数学不太好。现在他有一个问题，希望你帮他解答：
给定一元n次方程fx=c0+c1∗x+c2˙x2+...+cn˙xnf_x=c_0+c_1*x+c_2\dot{}{}x^2+...+c_n\dot{}{}x^n
定义fif_i的前k项和

sk∑i=0k−1fis_k\sum_{i=0}^{k-1}f_i

现给出n、n+1个各项的系数cic_i以及k，求sk%10007s_k\%10007

其中
Input
第1行输入T(1≤T≤10)，代表有T组数据。
紧接着每3行分别为n，各项系数，k，输入数据均为正整数。
Output
每组测试数据输出一行，输出fxf_x的前k-1项和$$
s_k\sum_{i=0}^{k-1}f_i

并对10007取模。 Sample Input 1 4 1 -2 3 1 0 3 Sample Output 21 Author Kirai ——————————————————————————————————————————— 这题用到了差分序列 详情见《组合数学(原书第5版)》翻译版 P169 查分序列: 设有一个序列$h_0,h_1,h_2,,,,h_n$ 它的一阶差分序列是

△h_i=h_{i+1}-h_i

对应二阶差分序列为对应二阶差分序列为

△^2h_i=△h_{i+1}-△h_i

由此得到差分表(看起来很难看啊意思意思就行了)由此得到差分表(看起来很难看啊 意思意思就行了)

h_0\ \ \ \ h_1\ \ \ \ h_2\ \ \ \ h_3 …\△h_0\ \ \ \ △h_1\ \ \ \ △h_2…\…

根据性质能够得到(证明看书吧..)根据性质能够得到(证明看书吧..)

h_x=\sum_{i=0}^{n}C(x,i)*△^ih_i

\sum_{i=0}^{n} \sum_{j=0}^{k-1}C(j,i)*△^ih_0

由由

\sum_{i=0}^{n}C(m,i) = C(n+1,m+1)

故故

\sum_{i=0}^{n} \sum_{j=0}^{k-1}C(j,i)*△^ih_0\ =\sum_{i=0}^{n}C(k,i+1)*△^ih_0

∗∗注：取模的时候最好都（x附本题代码———————————————————————————————————————————<!−−code0−−>**注：取模的时候最好都（x%MOD+MOD）%MOD** 附本题代码 ———————————————————————————————————————————

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
# include <bits/stdc++.h>
typedef long long int LL;
using namespace std;

# define abs(x) (((x)>0)?(x):-(x))

const LL N = 1e5+10;
const LL M = 10007;

/******************************************/
LL n,a[N],h[N],b[N];
LL k;

LL fac[M],inv[M];

LL qmod(LL a,LL b){
    LL res=1;
    while(b){
        if(b&1) res=res*a%M;
        b>>=1,a=a*a%M;
    }
    return res;
}

void init(){
    fac[0]=1;
    for(LL i=1;i<M;i++) fac[i]=fac[i-1]*i%M;
    inv[M-1]=qmod(fac[M-1],M-2);
    for(LL i=M-2;i>=0;i--) inv[i]=inv[i+1]*(i+1)%M;
}

LL C(LL n,LL m){
    return fac[n]*inv[m]%M*inv[n-m]%M;
}

LL Combination(LL n, LL m){
    if(n<m) return 0;
    if(n<M&&m<M) return C(n,m);
    return Combination(n/M,m/M)*Combination(n%M,m%M)%M;
}

int main(){
    init();
    LL _;scanf("%lld",&_);
    while(_--){
        scanf("%lld",&n);
        for(LL i=0;i<=n;i++) scanf("%lld",&a[i]),a[i]=a[i]%M;
        scanf("%lld",&k);
        for(LL i=0,j,x;i<=n;i++){
            for(h[i]=j=0,x=1;j<=n;j++){
                h[i]=(h[i]+a[j]*x%M)%M;
                h[i]=(h[i]%M+M)%M;x=x*i%M;
            }
        }

        b[0]=h[0];
        for(LL i=1;i<=n;i++){
            for(LL j=0;j<=n-i;j++)
                h[j]=(h[j+1]-h[j]+M)%M;
            b[i]=h[0];
        }

        LL ans = 0;
        for(LL i=0;i<=n;i++){
            ans = ans + b[i]*Combination(k,i+1)%M;
            ans = (ans%M+M)%M;
        }
        printf("%lld\n",ans);
    }
    return 0;
}