noip 아 날로 그 게임 cqbzoj 3391 (격자 경로 모델)

와, 시험 수학 은 정말 못 하 겠 다. 특히 이런 더러 운 시험 을 보 다 니.
제목 은 저작권 때문에 올 릴 수 없 지만 정 답 은 mod 라 고 알려 줄 수 있 습 니 다. 998244353
。。。
문제 풀이: (내 가 지금 기억 하고 있 을 때 빨리 써...)
먼저 기대 하 는 개념 을 말 해 보 자.
이 문제 가 요구 하 는 것 은 방안 의 기대 이다.
그러면 E = sigma (현재 프로젝트 가 나타 날 확률 * 현재 프로젝트 의 프로젝트 수)
확률 은 여기 서 1 / C (n, 2) 가 분명 하 다. 그러면 마지막 답 도 C (n, 2) 를 타 야 한다.
상쇄 되 었 기 때문에 실제 요구 하 는 것 은 방안 의 총수 이다.
i 번 째 상자 와 j 번 째 상 자 를 선택 할 때의 방안 수 를 고려 합 니 다.
모두 두 개의 작은 공 만 있 기 때문에 방안 수 는 C (a [i] + a [j] + b [i] + b [j], a [i] + a [j]) 와 같다.
한 줄 로 놓 을 자리 에서 흰 공 을 놓 을 자 리 를 고 르 는 거 예요.
그래서 직접 폭력 적 으로 해결 하 는 방안 이 나 왔 다. 모든 방안 을 열거 하고 화 해 를 구 했다.
시간 복잡 도 O (n ^ 2), 바로 폭발 (시험 때 이런 쓰레기 폭력 다 틀 렸 어...)
정 해 는 작은 공 문 제 를 네트워크 경로 로 바 꾸 는 문제 이다.
n * m 의 격자 그림 에 대해 (0, 0) 에서 (n, m) 까지 가 는 방안 수 는 C (n + m, n) 입 니 다.
이것 은 직접 얻 을 수 있 지만 dp 의 방식 으로 도 얻 을 수 있다.
dp[i][j]=dp[i][j-1]+dp[i-1][j]
이 dp 는 겹 쳐 서 만 들 수 있다 는 것 을 알 기 어렵 지 않다.
예 를 들 어:
dp 로 (0, 0) 에서 (n, m) 까지 의 방안 수 를 계산 할 때 우리 가 구 하 는 데 방해 가 되 지 않 습 니 다.
(1, 1) 부터 (n - 1, m - 1) 까지 의 값 은 dp [1] [1] + + 이면 됩 니 다.
그러나 여전히 할 수 없 으 며, 마이너스 좌 표를 도입 해 야 한다.
그러면 이 문제 에 대해 작은 공 을 읽 을 때 dp [- a [i] [- b [i]] +
그러면 i 번 째 상자 와 j 번 째 상자 로 구 성 된 방안 수 는 바로...
좌표 축 (- a [i], - b [i]) 에서 (a [j], b [j] 까지 의 dp 값
좌표 가 마이너스 인 경우 3000 개 만 더 하면 돼 요.
매 거 진 문 제 를 완벽 하 게 해결 하고 이전에 구 한 값 Orz 를 교묘 하 게 이용 했다.
마지막 으로 무 거 워 야 돼 요. 이렇게 같이 하면 dp [a [i] [- b [i] 부터 dp [a]] [b [i]] 가 나 와 요.
의 경우 이런 상황 을 빼 야 한다. 그리고 이미 i 와 j 를 선택 한 후에 j 와 i 를 다시 선택 할 것 이다.
이것 은 마지막 답안 을 2, 즉 2 를 곱 한 역 원 으로 나 누 면 된다.
이렇게 하면 할 수 있 고, 또 일부 세부 사항 은 코드 를 볼 수 있다.
code：

#include
#include
#include
#include
#include
#include

const int MAXC=12000;
const int MAXA=6000;
const int mod=998244353;
typedef long long LL;
using namespace std;
int jc[MAXC+10],rjc[MAXC+10];
int dp[MAXA+10][MAXA+10];
int cnt[3010][3010];
int n,a,b,sum,ans;

inline void prepare(){
    jc[0]=jc[1]=rjc[0]=rjc[1]=1;
    for(int i=2;i<=MAXC;i++)
    {
        jc[i]=1ll*jc[i-1]*i%mod;
        rjc[i]=1ll*(mod-mod/i)*rjc[mod%i]%mod;
    }
    for(int i=2;i<=MAXC;i++)
        rjc[i]=1ll*rjc[i]*rjc[i-1]%mod;
}
inline int C(int n,int k){
    return 1ll*jc[n]*rjc[k]%mod*rjc[n-k]%mod;
}
inline int add(int a,int b){
    return a+b>mod?a+b-mod:a+b;
}
inline void Read(int &Ret){
    char ch;bool flag=0;
    for(;ch=getchar(),!isdigit(ch);)if(ch=='-')flag=1;
    for(Ret=ch-'0';ch=getchar(),isdigit(ch);Ret=Ret*10+ch-'0');
    flag&&(Ret=-Ret);
}
int main()
{
    Read(n); prepare();
    for(int i=1;i<=n;i++)
    {
        Read(a); Read(b);
        sum=add(sum,C((a+b)<<1,a<<1));
        dp[-a+3000][-b+3000]++;
        cnt[a][b]++;
    }
    for(int i=0;i<=MAXA;i++)
        for(int j=0;j<=MAXA;j++)
        {
            if(i) dp[i][j]=add(dp[i][j],dp[i-1][j]);
            if(j) dp[i][j]=add(dp[i][j],dp[i][j-1]);
            if(i>=3000&&j>=3000&&cnt[i-3000][j-3000])
                ans=add(ans,1ll*dp[i][j]*cnt[i-3000][j-3000]%mod);
        }
    ans=add(mod,ans-sum);
    ans=1ll*ans*rjc[2]%mod;
    printf("%d
",ans);
}