結果

問題 No.886 Direct
ユーザー GinatiaGinatia
提出日時 2024-06-13 22:22:51
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 341 ms / 4,000 ms
コード長 4,191 bytes
コンパイル時間 1,868 ms
コンパイル使用メモリ 175,520 KB
実行使用メモリ 157,012 KB
最終ジャッジ日時 2024-06-13 22:23:07
合計ジャッジ時間 15,330 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 306 ms
156,840 KB
testcase_01 AC 303 ms
156,860 KB
testcase_02 AC 302 ms
156,792 KB
testcase_03 AC 307 ms
156,840 KB
testcase_04 AC 294 ms
156,776 KB
testcase_05 AC 304 ms
156,804 KB
testcase_06 AC 295 ms
156,832 KB
testcase_07 AC 285 ms
156,872 KB
testcase_08 AC 294 ms
156,880 KB
testcase_09 AC 341 ms
156,892 KB
testcase_10 AC 302 ms
156,876 KB
testcase_11 AC 304 ms
156,792 KB
testcase_12 AC 308 ms
156,776 KB
testcase_13 AC 324 ms
156,888 KB
testcase_14 AC 307 ms
156,916 KB
testcase_15 AC 299 ms
156,768 KB
testcase_16 AC 294 ms
156,908 KB
testcase_17 AC 302 ms
156,916 KB
testcase_18 AC 317 ms
156,804 KB
testcase_19 AC 305 ms
156,808 KB
testcase_20 AC 301 ms
156,828 KB
testcase_21 AC 299 ms
156,872 KB
testcase_22 AC 325 ms
156,836 KB
testcase_23 AC 314 ms
156,768 KB
testcase_24 AC 302 ms
156,796 KB
testcase_25 AC 299 ms
156,804 KB
testcase_26 AC 302 ms
156,876 KB
testcase_27 AC 313 ms
156,956 KB
testcase_28 AC 305 ms
156,896 KB
testcase_29 AC 301 ms
157,012 KB
testcase_30 AC 308 ms
156,852 KB
testcase_31 AC 313 ms
156,772 KB
testcase_32 AC 308 ms
156,860 KB
testcase_33 AC 313 ms
156,960 KB
testcase_34 AC 311 ms
156,808 KB
testcase_35 AC 303 ms
156,864 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:7:5: warning: inline variables are only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
    7 |     inline static constexpr T mod = MOD;
      |     ^~~~~~

ソースコード

diff # 

#include <bits/stdc++.h>
#include <vector>
using i64 = long long;


template <typename T, T MOD = 1000000007> struct Mint {
    inline static constexpr T mod = MOD;
    T v;
    Mint() : v(0) {}
    Mint(signed v) : v(v) {}
    Mint(long long t) {
        v = t % MOD;
        if (v < 0)
            v += MOD;
    }

    Mint pow(long long k) {
        Mint res(1), tmp(v);
        while (k) {
            if (k & 1)
                res *= tmp;
            tmp *= tmp;
            k >>= 1;
        }
        return res;
    }

    static Mint add_identity() { return Mint(0); }
    static Mint mul_identity() { return Mint(1); }

    Mint inv() { return pow(MOD - 2); }

    Mint &operator+=(Mint a) {
        v += a.v;
        if (v >= MOD)
            v -= MOD;
        return *this;
    }
    Mint &operator-=(Mint a) {
        v += MOD - a.v;
        if (v >= MOD)
            v -= MOD;
        return *this;
    }
    Mint &operator*=(Mint a) {
        v = 1LL * v * a.v % MOD;
        return *this;
    }
    Mint &operator/=(Mint a) { return (*this) *= a.inv(); }

    Mint operator+(Mint a) const { return Mint(v) += a; }
    Mint operator-(Mint a) const { return Mint(v) -= a; }
    Mint operator*(Mint a) const { return Mint(v) *= a; }
    Mint operator/(Mint a) const { return Mint(v) /= a; }

    Mint operator+() const { return *this; }
    Mint operator-() const { return v ? Mint(MOD - v) : Mint(v); }

    bool operator==(const Mint a) const { return v == a.v; }
    bool operator!=(const Mint a) const { return v != a.v; }
};
template <typename T, T MOD>
std::ostream &operator<<(std::ostream &os, Mint<T, MOD> m) {
    os << m.v;
    return os;
}
using Z = Mint<i64>;

struct Combination {
    std::vector<Z> fac, ifac;
    int N;
    Combination(int _N) : N(2 * _N), fac(2 * _N + 1), ifac(2 * _N + 1) {
      fac[0] = Z(1);
      for (int i = 1; i <= N; i++) {
        fac[i] = fac[i - 1] * Z(i);
      }
      ifac[N] = fac[N].inv();
      for (int i = N - 1; i >= 0; i--) {
        ifac[i] = ifac[i + 1] * Z(i + 1);
      }
    }

    Z C(int n, int k) {
        if (n < k or n < 0 or k < 0) {
            return Z(0);
        }
        return fac[n] * ifac[n - k] * ifac[k];
    }
    Z P(int n, int k) {
        if (n < k or n < 0 or k < 0) {
            return Z(0);
        }
        return fac[n] * ifac[n - k];
    }
    Z H(int n,int k){
      return C(n+k-1,n);
    }
    Z S(int n,int k){
      Z ans=0;
      for(i64 i=0;i<=k;i++){
        if((k-i)%2==0){
          ans+=C(k,i)*Z(i).pow(n);
        }
        else{
          ans-=C(k,i)*Z(i).pow(n);
        }
      }
      return ans*ifac[k];
    }

};

const int N=3e6;
std::vector<int>prime;
std::vector<bool>is_prime(N+1,true);
std::vector<int>mobius(N+1,1);

void sieve(){
    is_prime[0]=is_prime[1]=false;
    for(int p=2;p<=N;p++){
        if(!is_prime[p])continue;
        prime.push_back(p);
        mobius[p]=-1;
        for(int q=2*p;q<=N;q+=p){
            is_prime[q]=false;
            if((q/p)%p==0)mobius[q]=0;
            else mobius[q]=-mobius[p];
        }
    }
}

template<typename T>
std::vector<T> fast_zeta(std::vector<T>F){
    int n=F.size();
    for(int p=2;p<n;p++){
        if(!is_prime[p])continue;
        for(int k=(n-1)/p;k>=1;k--){
            F[k]+=F[k*p];
        }
    }
    return F;
}

template<typename T>
std::vector<T> fast_mobius(std::vector<T>f){
    int n=f.size();
    for(int p=2;p<n;p++){
        if(!is_prime[p])continue;
        for(int k=1;k*p<n;k++){
            f[k]-=f[k*p];
        }
    }
    return f;
}

template<typename T>
std::vector<T> gcd_conv(const std::vector<T>&f,const std::vector<T>&g){
    int n=std::max(f.size(),g.size());
    auto F=fast_zeta(f);
    auto G=fast_zeta(g);
    std::vector<T>H(n);
    for(int i=1;i<n;i++)H[i]=F[i]*G[i];
    return fast_mobius(H);
}

void solve()
{   
    int H,W;
    std::cin>>H>>W;
    Z ans=Z(H)*Z(W-1)+Z(W)*Z(H-1);
    int n=std::max(H,W);
    std::vector<Z>h(N),w(N);
    for(int i=0;i<H;i++)h[i]=H-i;
    for(int i=0;i<W;i++)w[i]=W-i;

    auto f=gcd_conv(h,w);
    ans+=f[1]*2;
    std::cout<<ans<<'\n';
}
int main()
{
    std::cin.tie(nullptr)->sync_with_stdio(false);
    sieve();
    solve();
}
0