結果
問題 |
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 |
ソースコード
#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; }