結果
問題 | No.2243 Coaching Schedule |
ユーザー |
|
提出日時 | 2023-03-13 15:24:28 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,928 bytes |
コンパイル時間 | 795 ms |
コンパイル使用メモリ | 88,872 KB |
最終ジャッジ日時 | 2025-02-11 10:55:11 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 14 TLE * 23 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:112:17: warning: format ‘%d’ expects argument of type ‘int*’, but argument 2 has type ‘LL*’ {aka ‘long long int*’} [-Wformat=] 112 | scanf("%d", &v); | ~^ ~~ | | | | | LL* {aka long long int*} | int* | %lld main.cpp:103:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 103 | scanf("%d %d", &m, &n); | ~~~~~^~~~~~~~~~~~~~~~~ main.cpp:112:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 112 | scanf("%d", &v); | ~~~~~^~~~~~~~~~
ソースコード
#include<stdio.h> #include<string.h> #include<stdlib.h> #include <map> #include <vector> #include <queue> #include <deque> #include <set> #include <stack> #include <algorithm> #include <array> #include <unordered_set> #include <unordered_map> #include <string> using namespace std; bool rcmp(int a, int b) { return a>b; } typedef long long LL; #define MOD 998244353 #define GGG 3 void assert(int *p) { *p=0; } int expit(LL b, LL m) { LL r=1; while(m) { if (m&1) { r=r*b; r%=MOD; } b=b*b; b%=MOD; m>>=1; } return r; } void fft(int *p, int n, char revert) { if ((MOD-1)%n) assert(0); int rt = expit(GGG, (MOD-1)/n); LL x, y; if (revert) { rt = expit(rt, MOD-2); } int b, i, j, l, t; LL w, ww, v, u, vv; for (i=1, j=0; i<n; i++) { b=n>>1; for (; j&b; b>>=1) j^=b; j^=b; if (i<j) { t=p[i]; p[i]=p[j]; p[j]=t; } } for (l=2; l<=n; l<<=1) { w=rt; for (i=l; i<n; i<<=1) w=(w*w)%MOD; for (i=0; i<n; i+=l) { ww=1; for (j=0; j<l/2; j++) { u=p[i+j]; v=p[i+j+l/2]; v*=ww; v%=MOD; vv=u+v; if (vv>=MOD) vv-=MOD; p[i+j]=vv; vv=u-v; if (vv<0) vv+=MOD; p[i+j+l/2]=vv; ww*=w; ww%=MOD; } } } if (revert) { x = expit(n, MOD-2); for (i=0; i<n; i++) { vv=p[i]; vv*=x; vv%=MOD; p[i]=vv; } } } #define MAXN 1<<20 int pbuf1[MAXN]; int pbuf2[MAXN]; int mpoly(int *p1, int c1, int *p2, int c2) { int m=c1+c2+1; int n=1; while(n<m) n<<=1; int i; LL v; for (i=0; i<=c1; i++) pbuf1[i]=p1[i]; for (; i<n; i++) pbuf1[i]=0; for (i=0; i<=c2; i++) pbuf2[i]=p2[i]; for (; i<n; i++) pbuf2[i]=0; fft(pbuf1, n, 0); fft(pbuf2, n, 0); for (i=0; i<n; i++) { v=pbuf1[i]; v*=pbuf2[i]; v%=MOD; pbuf1[i]=v; } fft(pbuf1, n, 1); i=n-1; while(i>0&&pbuf1[i]==0) i--; return i; } int ft[100004]; int cs[100004]; int kcs[100004]; int ift[100004]; int pa[200004]; int pb[200004]; int main() { int n, i, m, mx, j, k, c; LL v, r; scanf("%d %d", &m, &n); ft[0]=ift[0]=1; for (i=1; i<=n; i++) { v=ft[i-1]; v*=i; v%=MOD; ft[i]=v; ift[i]=expit(v, MOD-2); } for (i=1; i<=m; i++) cs[i]=0; for (i=0; i<n; i++) { scanf("%d", &v); cs[v]++; } k=0; for (i=1; i<=m; i++) if (cs[i]) kcs[k++]=cs[i]; mx = *max_element(kcs, kcs+k); for (i=0; i<mx; i++) pb[i]=0; for (; i<=n; i++) { v=1; for (j=0; j<k; j++) { c=kcs[j]; // i!/(i-c)! v*=ft[i]; v%=MOD; v*=ift[i-c]; v%=MOD; } v*=ift[i]; v%=MOD; pb[i]=v; } // for pa... for (i=0; i<=n; i++) { v=ift[i]; if (i&1) { v=MOD-v; v%=MOD; } pa[i]=v; } mpoly(pa, n, pb, n); r=0; for (i=0; i<=n; i++) { v=pbuf1[i]; v*=ft[i]; v%=MOD; r+=v; r%=MOD; } printf("%lld\n", r); return 0; }