C++14(g++5.4) 解法, 执行用时: 690ms, 内存消耗: 32148K, 提交时间: 2018-08-22 19:35:32

#include<bits/stdc++.h>
using namespace std;


typedef long long ll;
const int MAX_K = 45;
ll v[45]; int n, m, k;
ll bit[45][100005];
const ll mod = 1e9 + 7;

void add(int i, int x, ll y) {
	for (; i <= n; i += i & -i) bit[x][i] = (bit[x][i] + y) % mod;
}

ll sum(int i, int x) {
	ll res = 0;
	for (; i; i -= i & -i) res += bit[x][i];
	return res % mod;
}

int main() {
	cin >> n >> m >> k;
	v[1] = 1;
	for (int i = 2; i < 45; i++) {
		v[i] = v[mod%i] * (mod - mod / i) % mod;
	}
	k--;
	for (int i = 0; i < m; i++) {
		int x, y, z;
		scanf("%d", &y);
		if (y) {
			scanf("%d", &x);
			ll res = 0, u =1;
			for (int j = 0; j <= k; j++) {
				res = (res + sum(x,k-j)*u%mod) % mod;
				u = u * (x - j) % mod*v[j + 1]%mod;
				//if (u < 0) u += mod;
			}
			printf("%lld\n", res);
		}
		else {
			scanf("%d%d", &x, &z);
			ll u = 1;
			for (int j = 0; j <= k; j++) {
				add(x, j, u*z%mod);
				u = u * (k - x - j) % mod*v[j + 1]%mod;
				if (u < 0) u += mod;
			}
		}
	}
	//system("pause");
}

C++11(clang++ 3.9) 解法, 执行用时: 900ms, 内存消耗: 17652K, 提交时间: 2019-04-28 19:44:00

#include <bits/stdc++.h>
using namespace std;
const int p = 1000000007;
int n, m, k, inv[105], c[45][100005];
void R(int k, int x, int y) {
	for (; x <= n; x += x & -x)
		c[k][x] = (c[k][x] + y) % p;
}
int G(int k, int x) {
	int r = 0;
	for (; x > 0; x -= x & -x)
		r = (r + c[k][x]) % p;
	return r;
}
int main() {
	scanf("%d%d%d", &n, &m, &k);
	--k;
	inv[1] = 1;
	for (int i = 2; i < 105; ++i)
		inv[i] = (long long)inv[p % i] * (p - p / i) % p;
	for (int i = 1; i <= m; ++i) {
		int o, x, y;
		scanf("%d", &o);
		if (o == 0) {
			scanf("%d%d", &x, &y);
			long long u = 1;
			for (int j = 0; j <= k; ++j) {
				R(j, x, u * y % p);
				u = u * inv[j + 1] % p * (k - x - j) % p;
				if (u < 0)
					u += p;
			}
		} else {
			scanf("%d", &x);
			long long u = 1, r = 0;
			for (int j = 0; j <= k; ++j) {
				r = (r + u * G(k - j, x)) % p;
				u = u * inv[j + 1] % p * (x - j) % p;
			}
			printf("%lld\n", r);
		}
	}
	return 0;
}