結果
問題 | No.2013 Can we meet? |
ユーザー |
![]() |
提出日時 | 2022-07-16 00:54:07 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 346 ms / 2,500 ms |
コード長 | 2,472 bytes |
コンパイル時間 | 4,724 ms |
コンパイル使用メモリ | 268,392 KB |
最終ジャッジ日時 | 2025-01-30 09:23:21 |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 35 |
ソースコード
#include <stdio.h> #include <bits/stdc++.h> #include <atcoder/all> using namespace atcoder; using mint = modint998244353; using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf 1000000001 struct combi{ deque<mint> kaijou; deque<mint> kaijou_; combi(int n){ kaijou.push_back(1); for(int i=1;i<=n;i++){ kaijou.push_back(kaijou[i-1]*i); } mint b=kaijou[n].inv(); kaijou_.push_front(b); for(int i=1;i<=n;i++){ int k=n+1-i; kaijou_.push_front(kaijou_[0]*k); } } mint combination(int n,int r){ if(r>n)return 0; mint a = kaijou[n]*kaijou_[r]; a *= kaijou_[n-r]; return a; } mint junretsu(int a,int b){ mint x = kaijou_[a]*kaijou_[b]; x *= kaijou[a+b]; return x; } mint catalan(int n){ return combination(2*n,n)/(n+1); } }; void dfs(int l,int r,vector<mint> &dp,vector<mint> &c){ if(r-l<=1)return; int m = (l+r)/2; dfs(l,m,dp,c); vector<mint> x; for(int i=l;i<m;i++){ x.push_back(dp[i]); } vector<mint> y; rep(i,r-l+2){ y.push_back(c[i]); } x = convolution(x,y); for(int i=m;i<r;i++){ dp[i] -= x[i-l]; } dfs(m,r,dp,c); } int main(){ int n; cin>>n; int x0,y0,x1,y1; int dx,dy; cin>>x0>>y0>>x1>>y1; dx = abs(x0-x1); dy = abs(y0-y1); mint A,B; { int a,b; cin>>a>>b; int t = a+b; t *= 2; A = a; B = b; A /= t; B /= t; } vector<int> a(n); rep(i,n)cin>>a[i]; if(dx+dy>n*2){ cout<<0<<endl; return 0; } combi C(2000001); vector<mint> tc; { vector<mint> ta(n*2+1),tb(n*2+1); for(int i=dx;i<ta.size();i+=2){ mint t = A.pow(i); int diff = i - dx; t *= C.combination(i,diff/2); ta[i] = t; ta[i] *= C.kaijou_[i]; } for(int i=dy;i<ta.size();i+=2){ mint t = B.pow(i); int diff = i - dy; t *= C.combination(i,diff/2); tb[i] = t; tb[i] *= C.kaijou_[i]; } tc = convolution(ta,tb); rep(i,tc.size()){ tc[i] *= C.kaijou[i]; } } vector<mint> dp(n+1,0); rep(i,n+1){ dp[i] = tc[i*2]; } tc.resize(0); { vector<mint> ta(n+1),tb(n+1); rep(i,n+1){ ta[i] = A.pow(i*2); ta[i] *= C.combination(i*2,i); ta[i] *= C.kaijou_[i*2]; } rep(i,n+1){ tb[i] = B.pow(i*2); tb[i] *= C.combination(i*2,i); tb[i] *= C.kaijou_[i*2]; } tc = convolution(ta,tb); rep(i,tc.size()){ tc[i] *= C.kaijou[i*2]; } } dfs(0,dp.size(),dp,tc); mint ans = 0; rep(i,n){ ans += dp[i+1] * a[i]; } cout<<ans.val()<<endl; return 0; }