結果
問題 | No.1685 One by One |
ユーザー | 宋来恒 |
提出日時 | 2023-01-08 16:15:27 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 292 ms / 3,000 ms |
コード長 | 2,005 bytes |
コンパイル時間 | 576 ms |
コンパイル使用メモリ | 71,864 KB |
実行使用メモリ | 462,624 KB |
最終ジャッジ日時 | 2023-08-22 02:27:05 |
合計ジャッジ時間 | 7,919 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,492 KB |
testcase_01 | AC | 2 ms
5,496 KB |
testcase_02 | AC | 10 ms
40,576 KB |
testcase_03 | AC | 72 ms
205,580 KB |
testcase_04 | AC | 44 ms
165,696 KB |
testcase_05 | AC | 173 ms
298,228 KB |
testcase_06 | AC | 107 ms
271,400 KB |
testcase_07 | AC | 98 ms
244,500 KB |
testcase_08 | AC | 59 ms
199,344 KB |
testcase_09 | AC | 25 ms
96,100 KB |
testcase_10 | AC | 224 ms
395,124 KB |
testcase_11 | AC | 19 ms
73,388 KB |
testcase_12 | AC | 36 ms
138,904 KB |
testcase_13 | AC | 122 ms
278,176 KB |
testcase_14 | AC | 44 ms
153,216 KB |
testcase_15 | AC | 192 ms
357,648 KB |
testcase_16 | AC | 76 ms
248,284 KB |
testcase_17 | AC | 72 ms
241,712 KB |
testcase_18 | AC | 69 ms
239,484 KB |
testcase_19 | AC | 71 ms
240,596 KB |
testcase_20 | AC | 84 ms
235,172 KB |
testcase_21 | AC | 85 ms
235,144 KB |
testcase_22 | AC | 91 ms
245,368 KB |
testcase_23 | AC | 96 ms
249,392 KB |
testcase_24 | AC | 222 ms
421,580 KB |
testcase_25 | AC | 292 ms
442,916 KB |
testcase_26 | AC | 233 ms
439,036 KB |
testcase_27 | AC | 264 ms
426,976 KB |
testcase_28 | AC | 235 ms
462,420 KB |
testcase_29 | AC | 264 ms
462,624 KB |
testcase_30 | AC | 233 ms
462,476 KB |
testcase_31 | AC | 265 ms
462,476 KB |
testcase_32 | AC | 264 ms
462,336 KB |
testcase_33 | AC | 263 ms
462,528 KB |
testcase_34 | AC | 79 ms
247,600 KB |
testcase_35 | AC | 75 ms
247,184 KB |
testcase_36 | AC | 75 ms
255,864 KB |
testcase_37 | AC | 74 ms
253,620 KB |
testcase_38 | AC | 2 ms
4,376 KB |
testcase_39 | AC | 96 ms
255,668 KB |
testcase_40 | AC | 1 ms
4,376 KB |
testcase_41 | AC | 95 ms
255,748 KB |
testcase_42 | AC | 1 ms
4,376 KB |
testcase_43 | AC | 2 ms
5,528 KB |
testcase_44 | AC | 1 ms
4,376 KB |
testcase_45 | AC | 3 ms
5,552 KB |
testcase_46 | AC | 110 ms
319,904 KB |
testcase_47 | AC | 113 ms
319,992 KB |
testcase_48 | AC | 111 ms
320,088 KB |
testcase_49 | AC | 113 ms
319,960 KB |
ソースコード
#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <vector> using namespace std; #define fi first #define sc second #define mkp make_pair #define pii pair<int,int> typedef long long ll; const int N=8005,oo=1e9,mod=1e9+7; inline int read() { int x=0,flag=0;char ch=getchar(); while(ch<'0'||ch>'9') {flag|=(ch=='-');ch=getchar();} while('0'<=ch&&ch<='9') {x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return flag?-x:x; } inline int mx(int x,int y) {return x>y?x:y;} inline int mn(int x,int y) {return x<y?x:y;} inline void swp(int &x,int &y) {x^=y^=x^=y;} inline int as(int x) {return x>0?x:-x;} int n,m,C[N][N],S[N][N]; inline void prep() { C[0][0]=S[0][0]=1; C[1][0]=C[1][1]=1;S[1][0]=S[1][1]=1; for(int i=2;i<=m+n;++i) { C[i][0]=C[i][i]=1; for(int j=1;j<i;++j) C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod; for(int j=0;j<=i;++j) S[i][j]=(S[i-2][j]+C[i][j])%mod; } } inline void solve_odd() { int ans=0,L=n/2; for(int i=0;i<=L;++i) for(int j=0;j<=L;++j) { if(i==0&&j==0) continue; ans=(ans+1ll*C[n][i]*C[n-i][j]%mod*S[m-1][i+j-1])%mod; if(i<=j) { if(m-n-i+j<0) continue; ans=(ans+1ll*C[n][i]*C[n-i][j]%mod*S[m-n-i+j+(i+j-1)][i+j-1])%mod; } else { if(m-n-j+i<0) continue; ans=(ans+1ll*C[n][i]*C[n-i][j]%mod*S[m-n-j+i+(i+j-1)][i+j-1])%mod; } } if(m%2==0||m>=n) ans=(ans+1)%mod; printf("%d\n",ans); } inline void solve_even() { int ans=0,L=n/2; for(int i=0;i<=L;++i) for(int j=0;j<L;++j) { if(i==0&&j==0) continue; ans=(ans+1ll*C[n][i]*C[n-i][j]%mod*S[m-1][i+j-1])%mod; } if(m%2==0) ans=(ans+1)%mod; printf("%d\n",ans); } int main() { n=read();m=read(); if(m==0) { printf("1\n"); return 0; } prep(); if(n&1) solve_odd(); else solve_even(); return 0; }