作った問題「パスカルの三角形クエリ」の解法
※上手く書けなくて、途中から放棄してます
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; }