Fantasy of a Summation

题意

图片说明
给你n,K,mod,让你计算上面代码的结果

分析

这题很明显不能直接暴力，而要从每个元素贡献方面着手，也就是算一下每个元素会被加多少次。

举个例子

以第二个样例为例：
2 3 35000
1 2

1 2
1 2
1 2

第二排的1，上面共有2条路径，下面有两条路径。所以就是条路径，转换成公式就是

所以总和就是:

AC 代码

#include <iostream>
#include <algorithm>
#include <stdio.h>
using namespace std;
typedef long long ll;

ll T;
ll n,k,mod;
ll arr[1010];

ll ksm(ll a,ll b){
    ll res = 1;
    while(b){
        if(b&1) res = res*a%mod;
        a = a*a%mod;
        b>>=1;
    }
    return res;
}
ll solve(){
    ll res = 0;
    for(ll i = 0;i<n;i++){
        res = (res+arr[i]*ksm(n,k-1)%mod)%mod;
    }
    res = res*k%mod;
    return res;
}
int main(){
    cin>>T;
    int kase = 0;
    while(T--){
        scanf("%lld %lld %lld",&n,&k,&mod);
        for(int i = 0;i<n;i++) scanf("%lld",&arr[i]);
        ll res = solve();
        printf("Case %d: %lld\n",++kase,res);
    }
    return 0;
}