結果

問題 No.1001 注文の多い順列
コンテスト
ユーザー vjudge1
提出日時 2026-10-01 19:04:08
言語 C++14
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -lm -std=c++14 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 15 ms / 2,000 ms
+ 636µs
コード長 3,160 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 950 ms
コンパイル使用メモリ 189,044 KB
実行使用メモリ 9,864 KB
最終ジャッジ日時 2026-10-01 19:04:12
合計ジャッジ時間 3,398 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge4_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
bool Mbe;
using namespace std;
#define il inline
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair<int,int> pii;
typedef array<int,2> ai2;
il void ins(ai2&c, int d) {c[c[0]!=0]=d; }
// typedef pair<ll ,int> pli;
// typedef pair<ll,ll> pll;
#define fi first
#define se second
typedef vector<int> vi; 
template<typename t1> il bool cmax(t1&x, const t1&y) {return x<y?x=y,1:0; }
template<typename t1> il bool cmin(t1&x, const t1&y) {return y<x?x=y,1:0; }
#define sz(x) (int((x).size()))
#define pub push_back
const int mod=1e9+7;
il ll Mod(ll x) {return (x%mod+mod)%mod; } 
il ll qpow(ll a, ll    b   , ll re=1) {for (a%=mod; b; b&1?(re*=a)%=mod,1:0, (a*=a)%=mod, b>>=1);; return re;}
il ll  inv(ll a, ll b=mod-2, ll re=1) {for (a%=mod; b; b&1?(re*=a)%=mod,1:0, (a*=a)%=mod, b>>=1);; return re;}
const int  FN=3000; int fac[FN+3], ifac[FN+3];
il void MathInit(int n=FN) {
	fac[0]=ifac[0]=1; for (int i=1; i<=n; ++i) fac[i]=int((ll)fac[i-1]*i%mod), ifac[i]=int((ll)fac[i]*ifac[i-1]%mod); 
	for (int i=n, c=(int)inv(ifac[n]); i>=1; --i) 
		ifac[i]=int((ll)c*ifac[i-1]%mod), c=int((ll)c*fac[i]%mod);
}
il ll inv(int x) {return (ll)ifac[x]*fac[x-1]%mod; }
il ll C(int b, int a) {return b<a||a<0||b<0?0:(ll)fac[b]*ifac[b-a]%mod*ifac[a]%mod; }
const int N=3000;
pii p[N+3]; ll dp[2][N+3];
il void solve() {
    int n, tot[2]={0,0}; cin>>n, MathInit(n);
    for (int i=1; i<=n; ++i) cin>>p[i].se >> p[i].fi, p[i].fi-=p[i].se, tot[p[i].se]++;; //, fac[i]=int((ll)fac[i-1]*i%mod);
    sort(p+1, p+1+n), dp[0][0]=1;
    for (int i=1,o=1,fr0=0; i<=n; ++i,o^=1) {
        for (int j=0; j<=i; ++j) dp[o][j]=0;
        for (int j=0; j<=i; ++j) if (dp[o^1][j]) {
            if (p[i].se) {
                (dp[o][j+1]+=dp[o^1][j]*(p[i].fi-(fr0+j)))%=mod;
                (dp[o][ j ]+=dp[o^1][j])%=mod;
            } else {
                (dp[o][j]+=dp[o^1][j]*(p[i].fi-(fr0+j)))%=mod;
            }
            
        }
        fr0+=(p[i].se==0);
    }
    ll ans=0; for (int j=0; j<=tot[1]; ++j) (ans+=(j&1?-1:+1)*dp[n&1][j]*((ll)fac[n-(tot[0]+j)]))%=mod; // *ifac[]%mod
    cout << Mod(ans) << '\n';
}
bool Men;
int main() {
// g++ L26_1A.cpp -o L26_1A.exe -O2 -std=c++14 -Wall -Wextra -Wconversion -Wshadow -DMYFRE
// g++ Yukicoder1001.cpp -o Yukicoder1001.exe -O2 -std=c++14 -Wall -Wextra -Wconversion -Wshadow -DMYFRE
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#ifdef MYFRE
    cerr << "L26_1A Yukicoder1001" << endl;
    cerr << "L26_1A Yukicoder1001" << endl;
    cerr << "L26_1A Yukicoder1001" << endl;
    cerr << "M: " << db(&Mbe-&Men)/1024/1024 << endl;
    freopen("0.in", "r", stdin), freopen("0.out", "w", stdout);
#else 
    // freopen("Yukicoder1001.in", "r", stdin), freopen("Yukicoder1001.out", "w", stdout);
#endif
    // freopen()
    // MathInit();
    solve();//>>testid
    // int testid,testtt; cin>>testid>>testtt; for (int ti=1; ti<=testtt; ++ti) solve();
#ifdef MYFRE
    cerr << "T: " << (db)clock()/CLOCKS_PER_SEC << endl;
/*
copy Yukicoder1001\Yukicoder10011.in Yukicoder1001.in 
Yes
Yukicoder1001.exe
fc /W Yukicoder1001.out Yukicoder1001\Yukicoder10011.ans
*/
#endif    
}
0