結果
問題 | No.2206 Popcount Sum 2 |
ユーザー |
|
提出日時 | 2023-03-14 13:09:19 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 912 ms / 4,000 ms |
コード長 | 1,993 bytes |
コンパイル時間 | 701 ms |
コンパイル使用メモリ | 88,056 KB |
最終ジャッジ日時 | 2025-02-11 11:08:01 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 18 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:42:18: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 42 | int tc; scanf("%d", &tc); | ~~~~~^~~~~~~~~~~ main.cpp:43:31: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 43 | for (i=0; i<tc; i++) scanf("%d %d", &ns[i], &ms[i]); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
ソースコード
#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 998244353int expit(LL b, int e) {LL r=1;while(e) {if (e&1) { r*=b; r%=MOD; }b*=b; b%=MOD;e>>=1;}return r;}int bb[200004];int ss[200004];int ft[200004];int ift[200004];#define BB 500int xx[401][200004]; // (500+200000)*400/2int ns[200004];int ms[200004];int main() {int n, i, m, k, nn;int inv2 = expit(2, MOD-2);int xn;int tc; scanf("%d", &tc);for (i=0; i<tc; i++) scanf("%d %d", &ns[i], &ms[i]);xn=ns[0]; for (i=0; i<tc; i++) xn=max(xn, ns[i]);LL r, t, s;bb[0]=1;ft[0]=ift[0]=1;for (i=1; i<=xn+BB&&i<=200000; i++) {bb[i]=(bb[i-1]*2)%MOD;r=ft[i-1]; r*=i; r%=MOD;ft[i]=r;ift[i]=expit(r, MOD-2);}ss[0]=0; for (i=1; i<=xn; i++) ss[i]=(ss[i-1]+bb[i-1])%MOD;for (n=BB; n<=xn+BB&&n<=200000; n+=BB) {k = n/BB-1;s=0; for (m=0; m<=n; m++) {t=ft[n]; t*=ift[m]; t%=MOD; t*=ift[n-m]; t%=MOD;s+=t; s%=MOD;xx[k][m]=s;}}// while(tc) { tc--;// scanf("%d %d", &n, &m);for (i=0; i<tc; i++) {n=ns[i]; m=ms[i];n--; m--;k = (n+BB-1)/BB-1; if (k<0) k=0;nn = (k+1)*BB;r = xx[k][m];while(nn>n) {nn--;// move nn-> nn-1t=ft[nn]; t*=ift[m]; t%=MOD; t*=ift[nn-m]; t%=MOD;t+=r; t%=MOD; t*=inv2; t%=MOD;r=t;}// c(n-1, m-1)+...C(n-1, 0)// r=ft[n-1]; r*=ift[m-1]; r%=MOD; r*=ift[n-m]; r%=MOD;r*=ss[n+1]; r%=MOD;printf("%lld\n", r);}return 0;}