yukicoder : No.1489 Repeat Cumulative Sum

これもなんとか解けた。
https://yukicoder.me/problems/no/1489

問題

N行M列の行列のうち、1行目は全要素0であり、1列目の値が与えられている。
他の要素は、上と左の値の和であるものとする。
全要素の総和を求めよ。

解法

ある行の要素が、以降のn行までの間で何回分計上されるかを求めよう。
これは二項係数を式変形することで求めることができる。

あとは、その計上される回数と、対応する1列目の値の積の和を取っていく。

int N;
ll M;
int A[101010];
ll C[505050];
ll S[505050];
const ll mo=1000000007;
ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	ll P=1,Q=1;
	for(i=1;i<=N;i++) {
		P=P*((M-2+i)%mo)%mo;
		Q=Q*i%mo;
		C[i]=P*modpow(Q)%mo;
		(S[i]=S[i-1]+C[i])%=mo;
	}
	
	ll ret=0;
	FOR(i,N-1) {
		cin>>x;
		(ret+=x*(1+S[N-1-i]))%=mo;
	}
	cout<<ret<<endl;
	
}

まとめ

二項係数の式変形、いまだに苦手。