結果
問題 | No.1388 Less than K |
ユーザー |
![]() |
提出日時 | 2020-11-23 01:34:22 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,003 ms / 3,000 ms |
コード長 | 2,179 bytes |
コンパイル時間 | 1,704 ms |
コンパイル使用メモリ | 173,036 KB |
実行使用メモリ | 491,572 KB |
最終ジャッジ日時 | 2024-11-26 08:00:12 |
合計ジャッジ時間 | 15,805 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 74 |
ソースコード
#include<bits/stdc++.h>using namespace std;using ll = long long;#define fi first#define se secondconstexpr ll mod=998244353;const int MAX = 505000;ll fac[MAX], finv[MAX], inv[MAX];// テーブルを作る前処理void COMinit(){fac[0]=fac[1]=1;finv[0]=finv[1]=1;inv[1]=1;for(int i=2;i<MAX;i++){fac[i]=fac[i-1]*i%mod;inv[i]=mod-inv[mod%i]*(mod/i)%mod;finv[i]=finv[i-1]*inv[i]%mod;}}// 二項係数計算long long COM(int n,int k){if(n<k) return 0;if(n<0||k<0) return 0;return fac[n]*(finv[k]*finv[n-k]%mod)%mod;}void solve1(int h,int w,int k){int x=min(h,w);vector<vector<int>> dp(x+1,vector<int>(2*k+1,0));//dp[i][j] := move2 i times & distance j-kdp[0][k]=1;for(int i=0;i<=x;i++){for(int j=2*k;j>=0;j--){if(j-2>=0){dp[i][j-2]+=dp[i][j];if(dp[i][j-2]>mod){dp[i][j-2]-=mod;}}}if(i!=x){for(int j=0;j<=k;j++){int r=k-j,s=k+j;if(r+2<=2*k){dp[i+1][r+2]+=dp[i][r];if(dp[i+1][r+2]>mod){dp[i+1][r+2]-=mod;}}if(r!=s){r=s;if(r+2<=2*k){dp[i+1][r+2]+=dp[i][r];if(dp[i+1][r+2]>mod){dp[i+1][r+2]-=mod;}}}}}}ll ans=0;for(int i=0;i<=x;i++){ll way=dp[i][k];way*=(COM(h+w,h-i)*COM(w+i,w-i))%mod;way%=mod;ans+=way;ans%=mod;}cout<<ans<<endl;}void solve2(int h,int w,int k){int x=min(h,w);ll ans=0;for(int i=0;i<=x;i++){int kk=(k+2)/2;int a=1;ll way=COM(2*i,i);while(i-a*kk>=0){if(a%2==1){way-=2*COM(2*i,i-a*kk);way%=mod;}else{way+=2*COM(2*i,i-a*kk);way%=mod;}a++;}if(way<0){way+=mod*100;way%=mod;}way*=(COM(h+w,h-i)*COM(w+i,w-i))%mod;way%=mod;ans+=way;ans%=mod;}cout<<ans<<endl;}int main(){COMinit();int h,w,k;cin>>h>>w>>k;h--;w--;if(k<=300){solve1(h,w,k);}else{solve2(h,w,k);}}