WA求助
查看原帖
WA求助
670046
___w楼主2024/5/21 13:40

rt.

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define mk make_pair
#define ll long long
#define space putchar(' ')
#define enter putchar('\n')
using namespace std;

typedef vector <int> vi;
typedef pair <int, int> pii;

inline int rd() { int x = 0, f = 1; char c = getchar(); while (!isdigit(c)) f = c == '-' ? -1 : f, c = getchar(); while (isdigit(c)) x = (x<<3)+(x<<1)+(c^48), c = getchar(); return x*f; }
inline ll rdll() { ll x = 0, f = 1; char c = getchar(); while (!isdigit(c)) f = c == '-' ? -1 : f, c = getchar(); while (isdigit(c)) x = (x<<3)+(x<<1)+(c^48), c = getchar(); return x*f; }
template <typename T> inline void write(T x) { if (x < 0) x = -x, putchar('-'); if (x > 9) write(x/10); putchar(x%10+48); }

const int N = 2e5+5, M = 2005, mod = 1e9+7;
int n, ans, V = 2000, a[N], b[N], f[M*2][M*2], fac[M*4], ifac[M*4];

int qpow(int x, int y) { int k = 1; for (; y; y >>= 1, x = 1ll*x*x%mod) if (y&1) k = 1ll*k*x%mod; return k; }

int C(int x, int y) { if (x < 0 || y < 0 || x < y) return 0; return 1ll*fac[x]*ifac[y]%mod*ifac[x-y]%mod; }

void init(int n) {
	fac[0] = 1;
	for (int i = 1; i <= n; ++i) fac[i] = 1ll*fac[i-1]*i%mod;
	ifac[n] = qpow(fac[n], mod-2);
	for (int i = n-1; ~i; --i) ifac[i] = 1ll*ifac[i+1]*(i+1)%mod;
}

int main() {
	n = rd(); init(8000);
	for (int i = 1; i <= n; ++i) {
		a[i] = rd(), b[i] = rd();
		++f[-a[i]+V][-b[i]+V];
	}
	for (int i = 1; i < M*2; ++i)
		for (int j = 1; j < M*2; ++j)
			f[i][j] = (f[i][j]+(f[i-1][j]+f[i][j-1])%mod)%mod;
	for (int i = 1; i <= n; ++i) {
		ans = (ans+f[a[i]+V][b[i]+V])%mod;
		ans = (ans-C(2*a[i]+2*b[i], 2*a[i])+mod)%mod;
	}
	write(1ll*ans*qpow(2, mod-2)%mod);
	return 0;
}
2024/5/21 13:40
加载中...