作った問題「パスカルの三角形クエリ」の解法

※上手く書けなくて、途中から放棄してます
http://d.hatena.ne.jp/anta1/20130118/1358492699で書いた、作った問題の想定解法です。詳細はその記事を参照してください。

問題概略

「ある位置にパスカルの三角形の最初の何段かをmod1000000007で足す」というクエリをO(段数)くらいで処理して、最後に全部出力せよ

想定解法

一般化した累積和の逆を用いる。
通常の累積和・その逆ではある一定方向に対する和・差を取る。
しかしそれでは、多項式でないと効率的な形にできない。
まず、パスカルの三角形に下のような辺を張ってみる。

ここで、辺の向きは下向きとする。
この辺は「親の和が自分自身となる」といった性質や、「一番上まで行く経路の数が自分自身となる」といった性質がある。
この辺はパスカルの三角形(二項係数)の、DPでの計算を表していると見れる。
このとき、その辺の通りに累積和っぽいものをDPで取ればいい。下の部分が余るからそれ(O(サイズ)個)を引く。

コード

#include <cstdio>
int main() {
	static const long long MOD = 1000000007;
	int N, Q;
	static long long a[1111][1111];

	//二項係数を計算しておく
	static long long C[1111][1111];
	for(int i = 0; i <= 1000; i ++) {
		C[i][0] = 1;
		for(int j = 1; j <= i; j ++) {
			if((C[i][j] = C[i-1][j-1] + C[i-1][j]) >= MOD)
				C[i][j] -= MOD;
		}
	}

	scanf("%d", &N);
	scanf("%d", &Q);
	for(int ii = 0; ii < Q; ii ++) {
		int x, y, k;
		scanf("%d%d%d", &x, &y, &k);
		//三角形の頂点の座標に1を足す。するとその1が下に行き渡ってパスカルの三角形を形作る
		if((++ a[y][x]) >= MOD) a[y][x] -= MOD;
		//そのままではずっと下までいってしまうので、C(k,i)を引いてせきとめる
		for(int i = 0; i <= k; i ++) {
			if((a[y + k][x + i] += MOD - C[k][i]) >= MOD)
				a[y + k][x + i] -= MOD;
		}
	}
	
	//累積和の計算
	for(int i = 1; i < N; i ++) {
		(a[i][0] += a[i-1][0]) %= MOD;
		for(int j = 1; j <= i; j ++) {
			(a[i][j] += a[i-1][j] + a[i-1][j-1]) %= MOD;
		}
	}

	for(int i = 0; i < N; i ++) {
		for(int j = 0; j <= i; j ++) {
			printf("%I64d%c", a[i][j], j == i ? '\n' : ' ');
		}
	}
	return 0;
}