Submit Info #5643

Problem Lang User Status Time Memory
$\sum_{i=0}^{\infty} r^i i^d$ cpp hotman AC 4893 ms 230.05 MiB

ケース詳細
Name Status Time Memory
0_00 AC 2 ms 0.72 MiB
0_01 AC 64 ms 77.05 MiB
0_02 AC 4852 ms 230.02 MiB
2_00 AC 1 ms 0.67 MiB
2_01 AC 70 ms 77.05 MiB
2_02 AC 72 ms 77.30 MiB
2_03 AC 275 ms 84.77 MiB
2_04 AC 4893 ms 229.92 MiB
2_05 AC 4846 ms 230.05 MiB
example_00 AC 71 ms 77.05 MiB

#pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC push_options #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #include<bits/stdc++.h> #include <xmmintrin.h> #include <immintrin.h> using namespace::std; __attribute__((constructor))void init(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);} #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/priority_queue.hpp> #include<ext/pb_ds/tag_and_trait.hpp> // #include <boost/multiprecision/cpp_dec_float.hpp> // #include <boost/multiprecision/cpp_int.hpp> // namespace mp = boost::multiprecision; // typedef mp::number<mp::cpp_dec_float<0>> cdouble; // typedef mp::cpp_int cint; template<typename T>using pbds=__gnu_pbds::tree<T,__gnu_pbds::null_type,less<T>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>; template<typename T>using pbds_map=__gnu_pbds::tree<T,T,less<T>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>; template<typename T,typename E>using hash_map=__gnu_pbds::gp_hash_table<T,E>; template<typename T>using pqueue =__gnu_pbds::priority_queue<T, greater<T>,__gnu_pbds::rc_binomial_heap_tag>; typedef long long lint; #define INF (1LL<<60) #define IINF (1<<30) //#define EPS (1e-10) #define endl '\n' //#define MOD 1000000007LL #define MOD 998244353LL typedef vector<lint> vec; typedef vector<vector<lint>> mat; typedef vector<vector<vector<lint>>> mat3; typedef vector<string> svec; typedef vector<vector<string>> smat; template<typename T>inline void numout(T t){bool f=0;for(auto i:t){cout<<(f?" ":"")<<i<INF/2?i:"INF";f=1;}cout<<endl;} template<typename T>inline void numout2(T t){for(auto i:t)numout(i);} template<typename T>inline void output(T t){bool f=0;for(auto i:t){cout<<(f?" ":"")<<i;f=1;}cout<<endl;} template<typename T>inline void output2(T t){for(auto i:t)output(i);} template<typename T>inline void _output(T t){bool f=0;for(lint i=0;i<t.size();i++){cout<<f?"":" "<<t[i];f=1;}cout<<endl;} template<typename T>inline void _output2(T t){for(lint i=0;i<t.size();i++)output(t[i]);} #define rep(i,n) for(lint i=0;i<lint(n);++i) #define repi(i,a,b) for(lint i=lint(a);i<(lint)(b);++i) #define rrep(i,n) for(lint i=lint(n)-1;i>=0;--i) #define rrepi(i,a,b) for(lint i=lint(b)-1;i>=lint(a);--i) #define irep(i) for(lint i=0;;++i) #define all(n) begin(n),end(n) #define dist(a,b,c,d) sqrt(pow(a-c,2)+pow(b-d,2)) inline lint gcd(lint A,lint B){return B?gcd(B,A%B):A;} inline lint lcm(lint A,lint B){return A/gcd(A,B)*B;} // inline cint cgcd(cint A,cint B){return B?cgcd(B,A%B):A;} // inline cint clcm(cint A,cint B){return A/cgcd(A,B)*B;} inline bool chmin(auto& s,const auto& t){bool res=s>t;s=min(s,t);return res;} inline bool chmax(auto& s,const auto& t){bool res=s<t;s=max(s,t);return res;} const vector<lint> dx={1,0,-1,0,1,1,-1,-1}; const vector<lint> dy={0,1,0,-1,1,-1,1,-1}; #define SUM(v) accumulate(all(v),0LL) auto call=[](auto f,auto... args){return f(f,args...);}; class mint { using u64 = std::uint_fast64_t; public: u64 a; constexpr mint(const long long x = 0)noexcept:a(x>=0?x%get_mod():get_mod()-(-x)%get_mod()){} constexpr u64 &value()noexcept{return a;} constexpr const u64 &value() const noexcept {return a;} constexpr mint operator+(const mint rhs)const noexcept{return mint(*this) += rhs;} constexpr mint operator-(const mint rhs)const noexcept{return mint(*this)-=rhs;} constexpr mint operator*(const mint rhs) const noexcept {return mint(*this) *= rhs;} constexpr mint operator/(const mint rhs) const noexcept {return mint(*this) /= rhs;} constexpr mint &operator+=(const mint rhs) noexcept { a += rhs.a; if (a >= get_mod())a -= get_mod(); return *this; } constexpr mint &operator-=(const mint rhs) noexcept { if (a<rhs.a)a += get_mod(); a -= rhs.a; return *this; } constexpr mint &operator*=(const mint rhs) noexcept { a = a * rhs.a % get_mod(); return *this; } constexpr mint operator++(int n) noexcept { a += 1; if (a >= get_mod())a -= get_mod(); return *this; } constexpr mint operator--(int n) noexcept { if (a<1)a += get_mod(); a -= 1; return *this; } constexpr mint &operator/=(mint rhs) noexcept { return *this*= rhs.inv(); } constexpr bool operator==(mint x) noexcept { return a==x.a; } constexpr bool operator!=(mint x) noexcept { return a!=x.a; } constexpr static int root(){ mint root = 2; while(root.pow((get_mod()-1)>>1).a==1)root++; return root.a; } constexpr mint pow(long long n){ long long x=a; mint ret = 1; while(n>0) { if(n&1)(ret*=x); (x*=x)%=get_mod(); n>>=1; } return ret; } constexpr mint inv()const{ int x=a,y=get_mod(),u=1,v=0,t=0; while(y > 0) { t=x/y; x-=t*y;x^=y;y^=x;x^=y; u-=t*v;u^=v;v^=u;u^=v; } return mint(u); } mint comb(lint b){ using lint=long long; static bool init=1; static lint fac[10000011],ifac[10000011]; if(init){ init=0; fac[0]=1; ifac[0]=1; auto mod_pow=[&](lint x,lint n){ lint ans = 1; while(n != 0){ if(n&1)ans=ans*x%get_mod(); x=x*x%get_mod(); n=n>>1; } return ans; }; for(int i=0;i<10000010;i++){ fac[i+1]=fac[i]*(i+1)%get_mod(); ifac[i+1]=ifac[i]*mod_pow(i+1, get_mod()-2)%get_mod(); } } if(a==0&&b==0)return 1; if((lint)a<b||a<0)return 0; lint tmp=ifac[a-b]*ifac[b]%get_mod(); return tmp*fac[a]%get_mod(); } mint fact(){ using lint=long long; static bool init=1; static lint fac[10000011]; if(init){ init=0; fac[0]=1; for(int i=0;i<10000010;i++){ fac[i+1]=fac[i]*(i+1)%get_mod(); } } return fac[a]; } friend ostream& operator<<(ostream& lhs, const mint& rhs) noexcept { lhs << rhs.a; return lhs; } friend istream& operator>>(istream& lhs,mint& rhs) noexcept { lhs >> rhs.a; return lhs; } constexpr static u64 get_mod(){return MOD;} }; int main(){ lint n,x; cin>>x>>n; vector<mint>a(n),b(n); if(n==0){ cout<<mint(1)/mint(1-x)<<endl; return 0; } rep(i,n){ a[i]=mint(i+1).pow(n)*mint(n+1).fact()*mint(x).pow(i)+mint(i?a[i-1]:0); b[i]=mint(-1).pow(i)/(mint(i).fact()*mint(n+1-i).fact())*mint(x).pow(i); } mint eval=0; rep(i,n){ eval+=a[i]*b[n-1-i]; } cout<<eval*x/mint(1-x).pow(n+1)<<endl; }