結果
問題 | No.986 Present |
ユーザー |
![]() |
提出日時 | 2020-01-27 13:36:46 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 5 ms / 2,000 ms |
コード長 | 4,037 bytes |
コンパイル時間 | 1,593 ms |
コンパイル使用メモリ | 171,756 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-01 06:00:16 |
合計ジャッジ時間 | 2,494 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include<bits/stdc++.h>using namespace std;typedef unsigned long long int ull;typedef long long int ll;typedef pair<ll,ll> pll;typedef long double D;//typedef complex<D> P;#define F first#define S second//const ll MOD=1000000007;const ll MOD=998244353;template<typename T,typename U>istream & operator >> (istream &i,pair<T,U> &A){i>>A.F>>A.S; return i;}template<typename T>istream & operator >> (istream &i,vector<T> &A){for(auto &I:A){i>>I;} return i;}template<typename T,typename U>ostream & operator << (ostream &o,const pair<T,U> &A){o<<A.F<<" "<<A.S; return o;}template<typename T>ostream & operator << (ostream &o,const vector<T> &A){int i=A.size(); for(auto &I:A){o<<I<<(--i?" ":"");} return o;}template<long long int mod=1000000007>struct Mod_Int{typedef long long int ll;typedef pair<ll,ll> pll;typedef Mod_Int<mod> M;ll a;ll mod_pow(ll a,ll x){a%=mod;ll ans=1;for(int i=0;i<63;i++){if(x>>i&1){ans*=a; ans%=mod;}a*=a;a%=mod;}return ans;}pll Ex_gcd(ll a,ll b){if(b==0){return {1,0};}pll ret=Ex_gcd(b,a%b);ret.F-=a/b*ret.S;return {ret.S,ret.F};}ll prime_R(ll a){return mod_pow(a,mod-2);}ll R(ll a){ll ret=Ex_gcd(a,mod).F;ret%=mod;if(ret<0){ret+=mod;}return ret;}Mod_Int(ll A=1):a(A){a%=mod;if(a<0){a+=mod;}}Mod_Int(const M &b):a(b.a){}M & operator += (const M &b){a+=b.a;if(a>=mod){a-=mod;}return *this;}M operator + (const M &b) const {M c=*this;return c+=b;}M & operator -= (const M &b){a-=b.a;if(a<0){a+=mod;}return *this;}M operator - (const M &b) const {M c=*this;return c-=b;}M & operator *= (const M &b){(a*=b.a)%=mod;return *this;}M operator * (const M &b) const {M c=*this;return c*=b;}M & operator /= (const M &b){(a*=R(b.a))%=mod;return *this;}M operator / (const M &b) const {M c=*this;return c/=b;}M & mod_pow_equal(ll x){ll ans=1;while(x>0){if(x&1){ans*=a; ans%=mod;}a*=a;a%=mod;x>>=1;}a=ans;return *this;}M mod_pow(ll x){M c(a);return c.mod_pow_equal(x);}bool operator == (const M &b) const {return a==b.a;}bool operator != (const M &b) const {return a!=b.a;}bool operator <= (const M &b) const {return a<=b.a;}bool operator < (const M &b) const {return a<b.a;}bool operator > (const M &b) const {return a>b.a;}bool operator >= (const M &b) const {return a>=b.a;}M & operator = (const M &b){a=b.a;return *this;}M & operator = (const ll &b){(a=b)%=mod;if(a<0){a+=mod;}return *this;}};template<long long MOD>istream & operator >> (istream &i,Mod_Int<MOD> &A){ll a; cin>>a; A=Mod_Int<MOD>(a); return i;}template<long long MOD>ostream & operator << (ostream &i,const Mod_Int<MOD> &A){i<<A.a; return i;}using Int=Mod_Int<MOD>;//次元MでN本の独立なベクトルの列の本数Int regular(ll N,ll M){Int ret=1;Int all=Int(2).mod_pow(M);Int k=1;for(ll i=0;i<N;i++){ret*=all-k;k*=2;}return ret;}Int fact(ll N){Int ret=1;for(int i=1;i<=N;i++){ret*=i;}return ret;}Int regular_set(ll N,ll M){return regular(N,M)/fact(N);}int main(){cin.tie(0);ios::sync_with_stdio(false);ll N,M;cin>>N>>M;Int ans1=Int(2).mod_pow(N);Int ans2=regular_set(N,M);Int ans3=regular(M,M)/regular(N,N)/regular(M-N,M-N)/Int(2).mod_pow(N*(M-N));cout<<ans1<<" "<<ans2<<" "<<ans3<<endl;return 0;}