結果

問題 No.2747 Permutation Adjacent Sum
コンテスト
ユーザー MtSaka
提出日時 2024-04-20 15:40:10
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,841 bytes
コンパイル時間 2,416 ms
コンパイル使用メモリ 197,776 KB
最終ジャッジ日時 2025-02-21 06:45:43
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other TLE * 3 -- * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define overload(a,b,c,d,...) d
#define rep1(a) for(ll _=0;_<(ll)a;++_)
#define rep2(i,a) for(ll i=0;i<(ll)a;++i)
#define rep3(i,a,b) for(ll i=(ll)a;i<(ll)b;++i)
#define rep(...) overload(__VA_ARGS__,rep3,rep2,rep1)(__VA_ARGS__)
#define rrep1(i,a) for(ll i=(ll)a-1;i>=0;--i)
#define rrep2(i,a,b) for(ll i=(ll)b-1;i>=(ll)a;--i)
#define rrep(...) overload(__VA_ARGS__,rrep2,rrep1)(__VA_ARGS__)
#define eb emplace_back
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define lb(v,x) (lower_bound(all(v),x)-(v).begin())
#define ub(v,x) (upper_bound(all(v),x)-(v).begin())
using namespace std;
using ll=long long;
using vl=vector<ll>;
using ld=long double;
using i128=__int128_t;
template<typename T,typename U>inline static constexpr bool chmin(T&a,const U&b){return (a>b?a=b,true:false);}
template<typename T,typename U>inline static constexpr bool chmax(T&a,const U&b){return (a<b?a=b,true:false);}
static constexpr ll inf=numeric_limits<ll>::max()/2;
struct IOSetup{IOSetup(){ios::sync_with_stdio(false);cin.tie(nullptr);}};
template< typename T >
struct Combination {
  vector< T > _fact, _rfact, _inv;

  Combination(int sz) : _fact(sz + 1), _rfact(sz + 1), _inv(sz + 1) {
    _fact[0] = _rfact[sz] = _inv[0] = 1;
    for(int i = 1; i <= sz; i++) _fact[i] = _fact[i - 1] * i;
    _rfact[sz] /= _fact[sz];
    for(int i = sz - 1; i >= 0; i--) _rfact[i] = _rfact[i + 1] * (i + 1);
    for(int i = 1; i <= sz; i++) _inv[i] = _rfact[i] * _fact[i - 1];
  }

  inline T fact(int k) const { return _fact[k]; }

  inline T rfact(int k) const { return _rfact[k]; }

  inline T inv(int k) const { return _inv[k]; }

  T P(int n, int r) const {
    if(r < 0 || n < r) return 0;
    return fact(n) * rfact(n - r);
  }

  T C(int p, int q) const {
    if(q < 0 || p < q) return 0;
    return fact(p) * rfact(q) * rfact(p - q);
  }

  T H(int n, int r) const {
    if(n < 0 || r < 0) return (0);
    return r == 0 ? 1 : C(n + r - 1, r);
  }
};
template< typename T >
T lagrange_polynomial(const vector< T > &y, int64_t t) {
  int N = y.size() - 1;
  Combination< T > comb(N);
  if(t <= N) return y[t];
  T ret(0);
  vector< T > dp(N + 1, 1), pd(N + 1, 1);
  for(int i = 0; i < N; i++) dp[i + 1] = dp[i] * (t - i);
  for(int i = N; i > 0; i--) pd[i - 1] = pd[i] * (t - i);
  for(int i = 0; i <= N; i++) {
    T tmp = y[i] * dp[i] * pd[i] * comb.rfact(i) * comb.rfact(N - i);
    if((N - i) & 1) ret -= tmp;
    else ret += tmp;
  }
  return ret;
}
struct mint{
    private:
    static constexpr int mod=998244353;
    int x;
    public:
    mint():x(0){}
    mint(int x_):x(x_%mod){}
    int val()const{return x;}
    mint&operator+=(mint rhs){if((x+=rhs.x)>=mod)x-=mod;return (*this);}
    friend mint operator+(mint lhs,mint rhs){return lhs+=rhs;}
    mint&operator-=(mint rhs){if((x-=rhs.x)<0)x+=mod;return (*this);}
    friend mint operator-(mint lhs,mint rhs){return lhs-=rhs;}
    mint&operator*=(mint rhs){x=((long long)x*rhs.x)%mod;return (*this);}
    friend mint operator*(mint lhs,mint rhs){return lhs*=rhs;}
    mint pow(ll a)const{
        mint v=*this,res=1;
        while(a){
            if(a&1)res*=v;
            v=v*v;
            a>>=1;
        }
        return res;
    }
    mint inv()const{
        return pow(mod-2);
    }
    mint&operator/=(mint rhs){(*this)*=rhs.inv(); return (*this);}
    friend mint operator/(mint lhs,mint rhs){return lhs/=rhs;}
};
int main(){
    ll n,k;
    cin>>n>>k;
    /*
    sum[i=1,n-1](n-i)*(n-1)!*i^k
    =2*(n-1)!(n*sum[i=1,n-1]i^k - sum[i=1,n-1]i^{k+1}
    */
    vector<mint>a(k+3);
    a[0]=0;
    for(int i=1;i<k+3;++i){
        mint now=mint(i).pow(k);
        a[i]=a[i-1]+now*(mint(n)-i);
    }
    mint ans=lagrange_polynomial<mint>(a,n-1);
    for(int i=1;i<=n-1;++i)ans*=i;
    ans*=2;
    cout<<ans.val()<<endl;
}
0