Submit Info #5695

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

ケース詳細
Name Status Time Memory
0_00 AC 143 ms 155.05 MiB
0_01 AC 144 ms 155.05 MiB
0_02 AC 2800 ms 307.92 MiB
2_00 AC 144 ms 155.05 MiB
2_01 AC 145 ms 155.05 MiB
2_02 AC 147 ms 155.17 MiB
2_03 AC 265 ms 162.68 MiB
2_04 AC 2834 ms 307.92 MiB
2_05 AC 2785 ms 308.01 MiB
example_00 AC 145 ms 155.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 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 { u64 exp=get_mod()-2; while (exp) { if (exp % 2) { *this *= rhs; } rhs *= rhs; exp /= 2; } return *this; } 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(){ return pow(get_mod()-2); } static vector<mint> fac,ifac; static bool init; void build(){ init=0; fac.resize(10101011); ifac.resize(10101011); fac[0]=1,ifac[0]=1; for(int i=1;i<10101011;i++)fac[i]=fac[i-1]*i; ifac[10101010]=fac[10101010].inv(); for(int i=10101009;i>=0;i--)ifac[i]=ifac[i+1]*(i+1); } mint comb(lint b){ if(init)build(); if(a==0&&b==0)return 1; if((lint)a<b||a<0)return 0; return fac[a]*ifac[a-b]*ifac[b]; } mint fact(){ if(init)build(); 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;} }; vector<mint> mint::fac; vector<mint> mint::ifac; bool mint::init=1; mint lagrange_interpolation(vector<mint>v,lint n){ lint k=v.size(); if(n<k)return v[n]; mint tmp=1,ans=0; rep(i,k)tmp*=(n-i); rep(i,k){ ans+=v[i]*(tmp/(n-i))/(mint(k-1-i).fact()*mint(i).fact()*((n-i)%2?-1:1)); } return ans; } int main(){ lint a,k; cin>>a>>k; vector<mint>tmp(k+1),t(k+1); rep(i,k+1){ tmp[i]=mint(a).pow(i)*mint(i).pow(k)+mint(i?tmp[i-1]:0); } mint c=0,tmp2=mint(-a).pow(k); rep(i,k+1){ c+=tmp2*mint(k+1).comb(i+1)*tmp[i]; tmp2/=-a; } cout<<c*mint(1-a).pow(MOD-1-(k+1))<<endl; //rep(i,k+1)t[i]=(tmp[i]-c)/mint(a).pow(i); //cout<<lagrange_interpolation(t,n-1)*mint(a).pow(n-1)+c<<endl; }