結果

問題 No.1696 Nonnil
コンテスト
ユーザー 已经死了
提出日時 2025-08-06 13:15:54
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,195 bytes
コンパイル時間 3,273 ms
コンパイル使用メモリ 282,204 KB
実行使用メモリ 12,288 KB
最終ジャッジ日時 2025-08-06 13:16:04
合計ジャッジ時間 7,573 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 2
other AC * 9 WA * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define i64 long long
const int MOD=998244353;

int addm(int a,int b){ a+=b; if(a>=MOD) a-=MOD; if(a<0) a+=MOD; return a; }
int mulm(i64 a,i64 b){ return int((a*b)%MOD); }
int pw(i64 a,i64 e){ i64 r=1%MOD; a%=MOD; while(e){ if(e&1) r=r*a%MOD; a=a*a%MOD; e>>=1; } return int(r); }

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    i64 n; int k; 
    if(!(cin>>n>>k)) return 0;
    int m; cin>>m;
    vector<int>L(k+1,0);
    for(int i=0;i<m;i++){
        int l,r; cin>>l>>r;
        if(r>=1 && r<=k) L[r]=max(L[r],l); // 同右端点取最大的l
    }

    // 计数：在1..k中选t个位置，使每个限制区间都有至少一个被选位置
    vector<vector<int>> dp(k+1,vector<int>(k+1,0));
    dp[0][0]=1;
    for(int i=1;i<=k;i++){
        dp[i][0]=dp[i-1][0];
        if(L[i]) dp[i][0]=addm(dp[i][0],-dp[L[i]-1][0]);
        for(int j=1;j<=i;j++){
            int v=addm(dp[i-1][j],dp[i-1][j-1]);       // 选/不选i
            if(L[i]) v=addm(v,-dp[L[i]-1][j]);         // 保证[L[i],i]内至少选1个
            dp[i][j]=v;
        }
    }
    vector<int> cnt=dp[k]; // cnt[t]：满足限制的大小为t的子集个数

    // 预处理C(t,s)与s^n
    vector<int> fact(k+1,1),invf(k+1,1);
    for(int i=1;i<=k;i++) fact[i]=mulm(fact[i-1],i);
    invf[k]=pw(fact[k],MOD-2);
    for(int i=k;i>=1;i--) invf[i-1]=mulm(invf[i],i);
    auto C=[&](int n,int r)->int{
        if(r<0||r>n) return 0;
        return mulm(fact[n],mulm(invf[r],invf[n-r]));
    };
    vector<int> p(k+1,0);
    for(int s=0;s<=k;s++) p[s]=pw(s,n);

    // surj[t] = t!S(n,t) = sum_{s=0..t} C(t,s)*(-1)^{t-s}*s^n
    vector<int> surj(k+1,0);
    for(int t=0;t<=k;t++){
        int v=0;
        for(int s=0;s<=t;s++){
            int term=mulm(C(t,s),p[s]);
            if((t-s)&1) v=addm(v,-term); else v=addm(v,term);
        }
        surj[t]=v;
    }

    // 汇总答案：对每个t，选择的位置集合大小为t，然后把n个不同球映射到这t个已选盒子且每个非空
    int lim=min<i64>(k,n);
    int ans=0;
    for(int t=0;t<=lim;t++) ans=addm(ans,mulm(cnt[t],surj[t]));
    cout<<ans<<"\n";
    return 0;
}
0