結果
問題 | No.2381 Gift Exchange Party |
ユーザー |
|
提出日時 | 2023-07-14 21:35:19 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 18 ms / 2,000 ms |
コード長 | 1,215 bytes |
コンパイル時間 | 2,813 ms |
コンパイル使用メモリ | 244,428 KB |
実行使用メモリ | 19,936 KB |
最終ジャッジ日時 | 2024-09-16 06:26:56 |
合計ジャッジ時間 | 4,001 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 22 |
ソースコード
// Counting Template#include<bits/stdc++.h>using namespace std;#define mod 998244353#define FACSIZE 1048576long long power(long long a,long long b){long long x=1,y=a;while(b>0){if(b&1ll){x=(x*y)%mod;}y=(y*y)%mod;b>>=1;}return x%mod;}long long modular_inverse(long long n){return power(n,mod-2);}long long factorial[FACSIZE];long long invfact[FACSIZE];void cfact(){long long i;factorial[0]=1;factorial[1]=1;for(i=2;i<FACSIZE;i++){factorial[i]=factorial[i-1]*i;factorial[i]%=mod;}invfact[FACSIZE-1]=modular_inverse(factorial[FACSIZE-1]);for(i=FACSIZE-2;i>=0;i--){invfact[i]=invfact[i+1]*(i+1);invfact[i]%=mod;}}long long calcnCr(long long n,long long k){if(k<0 || n<k){return 0;}return (factorial[n]*((invfact[k]*invfact[n-k])%mod))%mod;}int main(){cfact();ios::sync_with_stdio(false);cin.tie(nullptr);long long n,p;cin >> n >> p;long long res=1;long long del=1;for(long long i=1;i*p<=n;i++){del*=calcnCr(n-(i-1)*p,p);del%=mod;del*=factorial[p-1];del%=mod;res+=(del*invfact[i]);res%=mod;}res=(mod+factorial[n]-res)%mod;cout << res << "\n";return 0;}