結果

問題 No.1001 注文の多い順列
ユーザー 👑 SPD_9X2
提出日時 2025-07-22 03:02:24
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 179 ms / 2,000 ms
コード長 1,399 bytes
コンパイル時間 463 ms
コンパイル使用メモリ 82,180 KB
実行使用メモリ 77,272 KB
最終ジャッジ日時 2025-07-22 03:02:29
合計ジャッジ時間 5,011 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

"""

https://yukicoder.me/problems/no/1001

包除原理らしい？

とりあえず、t=0 は絶対満たすようにする。

t=1を包除すると考えると、奇数個確定で違反する場合に負の寄与になるようにすればいいか
X順でsortして、dp[i][k] = i番目まで決めて、k個は確定で違反しているときの場合の数
で、最後に足し合わせればok?

3
0 1
1 1
1 2

"""

mod = 10**9+7

N = int(input())

fac = [1,1]
for i in range(2,N+10):
    fac.append(fac[-1] * i % mod)

Xt = []
tsum = 0

for i in range(N):
    t,X = map(int,input().split())
    if t == 1:
        X -= 1
    Xt.append( (X,t) )
    tsum += t

Xt.sort()

dp = [0] * (tsum+1)
dp[0] = 1

tsum = 0
for i in range(N):

    X,t = Xt[i]
    ndp = [0] * len(dp)

    last_zero = i - tsum

    if t == 0:
        for j in range(len(dp)):
            ndp[j] += dp[j] * (X-last_zero-j)
            ndp[j] %= mod
    else:
        for j in range(len(dp)):
            ndp[j] += dp[j]
            ndp[j] %= mod
            if j != len(dp)-1:
                ndp[j+1] += dp[j] * (X-last_zero-j)
                ndp[j+1] %= mod
    
    tsum += t
    dp = ndp

#print (dp)
for i in range(len(dp)):
    dp[i] *= fac[tsum-i]
    dp[i] %= mod

#print (dp)
ans = 0
for i in range(len(dp)):
    if i % 2 == 0:
        ans += dp[i]
    else:
        ans -= dp[i]
    ans %= mod

print (ans)
0