結果
問題 | No.2742 Car Flow |
ユーザー |
|
提出日時 | 2024-04-21 03:40:09 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 29 ms / 2,000 ms |
コード長 | 1,905 bytes |
コンパイル時間 | 2,923 ms |
コンパイル使用メモリ | 244,752 KB |
実行使用メモリ | 19,928 KB |
最終ジャッジ日時 | 2024-10-13 02:00:38 |
合計ジャッジ時間 | 5,395 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 50 |
ソースコード
// Counting Template #include<bits/stdc++.h> using namespace std; #define mod 998244353 #define FACSIZE 1048576 long long power(long long a,long long b){ long long x=1,y=a; while(b>0){ if(b&1ll){ x=(x*y)%mod; } y=(y*y)%mod; b>>=1; } return x%mod; } long long modular_inverse(long long n){ return power(n,mod-2); } long long factorial[FACSIZE]; long long invfact[FACSIZE]; void cfact(){ long long i; factorial[0]=1; factorial[1]=1; for(i=2;i<FACSIZE;i++){ factorial[i]=factorial[i-1]*i; factorial[i]%=mod; } invfact[FACSIZE-1]=modular_inverse(factorial[FACSIZE-1]); for(i=FACSIZE-2;i>=0;i--){ invfact[i]=invfact[i+1]*(i+1); invfact[i]%=mod; } } long long calcnCr(long long n,long long k){ if(k<0 || n<k){return 0;} return (factorial[n]*((invfact[k]*invfact[n-k])%mod))%mod; } long long solve(){ long long n; cin >> n; long long p=0,q=0; for(long long i=0;i<n;i++){ long long a; cin >> a; p+=a; q++; } p=min(p,n-p); return (p*modular_inverse(q))%mod; } int main(){ cfact(); ios::sync_with_stdio(false); cin.tie(nullptr); int t=1; // cin >> t; while(t>0){ t--; cout << solve()%mod << "\n"; } return 0; } // #include<bits/stdc++.h> // // using namespace std; // // vector<int> f(vector<int> &a){ // int n=a.size(); // vector<int> res; // for(int i=0;i<n;i++){ // if(a[(i+n-1)%n]==1 && a[i]==0){ // res.push_back(1); // continue; // } // else if(a[i]==1 && a[(i+1)%n]==1){ // res.push_back(1); // continue; // } // else{ // res.push_back(0); // } // } // return res; // } // // int main(){ // ios::sync_with_stdio(false); // cin.tie(nullptr); // vector<int> a={1,1,0}; // for(int tr=0;tr<10;tr++){ // for(auto &nx : a){cout << nx << " ";} // cout << "\n"; // a=f(a); // } // return 0; // }