Submission #6871126


Source Code Expand

Copy
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;

// template {{{  0 
// using {{{ 1
using ll = long long int;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vii = vector<pii>;
using vll = vector<pll>;
// }}} 1
// definition {{{ 1
// scaning {{{ 2
#define Scd(x) scanf("%d", &x)
#define Scd2(x,y) scanf("%d%d", &x, &y)
#define Scd3(x,y,z) scanf("%d%d%d", &x, &y, &z)
#define Scll(x) scanf("%lld", &x)
#define Scll2(x,y) scanf("%lld%lld", &x, &y)
#define Scll3(x,y,z) scanf("%lld%lld%lld", &x, &y, &z)
#define Scc(c) scanf("%c", &c);
#define Scs(s) scanf("%s", s);
#define Scstr(s) scanf("%s", &s);
// }}} 2
// constants {{{ 2
#define EPS (1e-7)
#define INF (2e9)
#define PI (acos(-1))
// }}} 2
// systems {{{ 2
#define Repe(x,y,z) for(ll x = z; x < y; x++)
#define Rep(x,y) Repe(x,y,0)
#define RRepe(x,y,z) for(ll x = y-z-1; x >= 0; x--)
#define RRep(x,y) RRepe(x,y,0)
// }}} 2
// output {{{ 2
#define YesNo(a) (a)?printf("Yes\n"):printf("No\n")
#define YESNO(a) (a)?printf("YES\n"):printf("NO\n")
// }}} 2
// }}} 1
// input {{{ 1
// }}} 1
// }}} 0

const long long int mod = 998244353;

// PowMod( base, index, modulo) return base ** index % modulo {{{
// PowMod = base ** index % mod ( natural numbers )
inline constexpr long long int PowMod( long long int base, long long int index, long long int modulo = mod ){
    // O( log(index) )
    long long int ret = 1;
    while( index ){
        if( index&1 ) (ret *= base) %= mod;
        (base *= base) %= mod;
        index >>= 1;
    }
    return ret;
}
// }}}
// CombMod( n, r, modulo ) return nCr % modulo {{{
// CombMod(ination) = nCr % mod ( natural number )
inline constexpr long long int CombMod( long long int n, long long int r, long long int modulo = mod){
    if( n < r ) return CombMod(r,n,modulo);
    long long int Upper = 1;
    long long int Lower = 1;
    for(long long int i = 0; i < r; i++){
        Upper = Upper * (n-i) % modulo;
        Lower = Lower * (i+1) % modulo;
    }
    // Return (Upper / Lower)
    long long int ret = Upper * PowMod(Lower,modulo-2,modulo) % modulo;
    return ret;
}
// }}}
// FactMod( n, modulo ) return n! % modulo {{{
// Fact(orial) = n! % mod ( natural number )
inline constexpr long long int Fact( long long int n, long long int modulo = mod){
    long long int Upper = 1;
    for(long long int i = 0; i < n; i++){
        Upper = Upper * (n-i) % modulo;
    }
    return Upper;
}
// }}}
// modint {{{

struct modint{
    long long int a;
    inline constexpr modint( long long int x = 0 ) noexcept : a(x % mod) {}
    inline constexpr long long int &value() noexcept { return a; }
    inline constexpr const long long int &value() const noexcept { return a; }
    inline constexpr modint operator+(const modint rhs) const noexcept{ return modint(*this) += rhs; }
    inline constexpr modint operator+(const int rhs) const noexcept{ return modint(*this) += rhs; }
    inline constexpr modint operator+(const long long int rhs) const noexcept{ return modint(*this) += rhs; }
    inline constexpr modint operator-(const modint rhs) const noexcept{ return modint(*this) -= rhs; }
    inline constexpr modint operator-(const int rhs) const noexcept{ return modint(*this) -= rhs; }
    inline constexpr modint operator-(const long long int rhs) const noexcept{ return modint(*this) -= rhs; }
    inline constexpr modint operator*(const modint rhs) const noexcept{ return modint(*this) *= rhs; }
    inline constexpr modint operator*(const int rhs) const noexcept{ return modint(*this) *= rhs; }
    inline constexpr modint operator*(const long long int rhs) const noexcept{ return modint(*this) *= rhs; }
    inline constexpr modint operator/(const modint rhs) const noexcept{ return modint(*this) /= rhs; }
    inline constexpr modint operator/(const int rhs) const noexcept{ return modint(*this) /= rhs; }
    inline constexpr modint operator/(const long long int rhs) const noexcept{ return modint(*this) /= rhs; }
    inline constexpr modint operator+=(const modint rhs) noexcept{ a += rhs.a; if( a >= mod ) a -= mod; return *this; }
    inline constexpr modint operator-=(const modint rhs) noexcept{ a -= rhs.a; if( a < 0 ) a += mod; return *this; }
    inline constexpr modint operator*=(const modint rhs) noexcept{ a = a * rhs.a % mod ;  return *this; }
    inline constexpr modint operator/=(const modint rhs) noexcept{ a = a * PowMod(rhs.a,mod-2) % mod; return *this; }
};

// }}}


int main() {

    ll N,M;
    Scll2(N,M);

    vector<modint> f(N+3*M+3,1);
    vector<modint> fr(N+3*M+3,1);

    Rep(i,f.size()-1){
        f[i+1] = f[i] * (i+1);
        fr[i+1] = fr[i] / (i+1);
    }

    // N_H_3M = N+3M-1_C_3M
    modint ans = f[N+3*M-1]*fr[3*M]*fr[N-1];
    modint t;

    for( int i = 2*M+1; i < 3*M+1; i++ ){
        t = f[N+3*M-i-2]*fr[3*M-i]*fr[N-2]*N;
        ans -= t;
    }

    for( int i = M-1; i >= 0; i-- ){
        if( 3*M-2*i > N ) break;
        t  = f[N+i-1] * fr[i] * fr[N-1];
        t *= f[N] * fr[3*M-2*i] * fr[N-3*M+2*i];
        ans -= t;
    }

    printf ("%lld\n", ans );

    return 0;
}

Submission Info

Submission Time
Task C - GP 2
User nishionyama
Language C++14 (GCC 5.4.1)
Score 900
Code Size 5259 Byte
Status AC
Exec Time 409 ms
Memory 39296 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:144:27: warning: format ‘%lld’ expects argument of type ‘long long int’, but argument 2 has type ‘modint’ [-Wformat=]
     printf ("%lld\n", ans );
                           ^
./Main.cpp:118:15: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     Scll2(N,M);
               ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 900 / 900
Status
AC × 4
AC × 26
Set Name Test Cases
Sample sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt
All 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt
Case Name Status Exec Time Memory
01-01.txt AC 1 ms 256 KB
01-02.txt AC 243 ms 23424 KB
01-03.txt AC 134 ms 13056 KB
01-04.txt AC 136 ms 13056 KB
01-05.txt AC 150 ms 14592 KB
01-06.txt AC 135 ms 13056 KB
01-07.txt AC 252 ms 24320 KB
01-08.txt AC 205 ms 19840 KB
01-09.txt AC 134 ms 12928 KB
01-10.txt AC 364 ms 34944 KB
01-11.txt AC 321 ms 30848 KB
01-12.txt AC 370 ms 35712 KB
01-13.txt AC 223 ms 21632 KB
01-14.txt AC 282 ms 27136 KB
01-15.txt AC 212 ms 20480 KB
01-16.txt AC 409 ms 39296 KB
01-17.txt AC 163 ms 15872 KB
01-18.txt AC 162 ms 15872 KB
01-19.txt AC 162 ms 15872 KB
01-20.txt AC 246 ms 23680 KB
01-21.txt AC 246 ms 23680 KB
01-22.txt AC 246 ms 23680 KB
sample-01.txt AC 1 ms 256 KB
sample-02.txt AC 1 ms 256 KB
sample-03.txt AC 1 ms 256 KB
sample-04.txt AC 43 ms 4096 KB