#492638 (C++17) No.1073 無限すごろく

提出ソース

結果

問題	No.1073 無限すごろく
ユーザー	Imperi_Night
提出日時	2020-06-05 21:47:29
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	2 ms / 2,000 ms
コード長	8,072 bytes
コンパイル時間	1,458 ms
コンパイル使用メモリ	135,572 KB
実行使用メモリ	6,824 KB
最終ジャッジ日時	2024-12-17 14:11:35
合計ジャッジ時間	2,102 ms
ジャッジサーバーID （参考情報）	judge1 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	1 ms 6,816 KB
testcase_02	AC	1 ms 6,820 KB
testcase_03	AC	2 ms 6,816 KB
testcase_04	AC	2 ms 6,816 KB
testcase_05	AC	2 ms 6,816 KB
testcase_06	AC	2 ms 6,816 KB
testcase_07	AC	2 ms 6,824 KB
testcase_08	AC	1 ms 6,820 KB
testcase_09	AC	1 ms 6,816 KB
testcase_10	AC	2 ms 6,816 KB
testcase_11	AC	2 ms 6,820 KB
testcase_12	AC	2 ms 6,820 KB
testcase_13	AC	2 ms 6,820 KB
testcase_14	AC	2 ms 6,816 KB
testcase_15	AC	2 ms 6,816 KB
testcase_16	AC	2 ms 6,820 KB
testcase_17	AC	2 ms 6,816 KB
testcase_18	AC	2 ms 6,820 KB
testcase_19	AC	2 ms 6,816 KB
testcase_20	AC	2 ms 6,820 KB
testcase_21	AC	2 ms 6,816 KB
testcase_22	AC	2 ms 6,816 KB
testcase_23	AC	2 ms 6,820 KB
testcase_24	AC	2 ms 6,816 KB
testcase_25	AC	2 ms 6,816 KB
testcase_26	AC	1 ms 6,816 KB
testcase_27	AC	2 ms 6,820 KB
testcase_28	AC	1 ms 6,816 KB
testcase_29	AC	1 ms 6,816 KB
testcase_30	AC	1 ms 6,816 KB
testcase_31	AC	2 ms 6,820 KB
testcase_32	AC	2 ms 6,820 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cstdint>
#include <cstdlib>
#include <cmath>
#include <complex>
#include <chrono>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>
#include <random>
#include <utility>
#include <limits>
#include <list>
#include <type_traits>

/* template start */
 
#define rep(i, a, b) for (long long i = (a); (i) < (b); (i)++)
#define all(i) i.begin(), i.end()

#ifdef LOCAL
#define debug(...) std::cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif

void debug_out(){std::cerr<<std::endl;}

template<typename Head,typename... Tail>
void debug_out(Head h,Tail... t){
  std::cerr<<" "<<h;
  if(sizeof...(t)>0)std::cout<<" :";
  debug_out(t...);
}
 
template <typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, std::pair<T1, T2> pa) {
  return os << pa.first << " " << pa.second;
}
 
template <typename T>
std::ostream& operator<<(std::ostream& os, std::vector<T> vec) {
  for (std::size_t i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " ");
  return os;
}
 
template<typename T1,typename T2>
inline bool chmax(T1& a,T2 b){return a<b && (a=b,true);}
 
template<typename T1,typename T2>
inline bool chmin(T1& a,T2 b){return a>b && (a=b,true);}

template<typename Num>
constexpr Num mypow(Num a, long long b) {
  if(b==0)return 1;
  if (a==0)return 0;
  Num x = 1;
  while (b > 0) {
    if(b & 1)x*=a;
    a*=a;
    b >>= 1;
  }
  return x;
}

template <std::uint_fast64_t Modulus> class modint {
  using u64 = std::uint_fast64_t;

public:
  u64 a;

  constexpr modint(const u64 x = 0) noexcept : a(x % Modulus) {}
  constexpr u64 &value() noexcept { return a; }
  constexpr const u64 &value() const noexcept { return a; }
  constexpr bool operator==(const modint rhs) const noexcept {return a==rhs.a;}
  constexpr bool operator!=(const modint rhs) const noexcept {return !(*this==rhs);}
  constexpr modint operator+(const modint rhs) const noexcept {
    return modint(*this) += rhs;
  }
  constexpr modint operator-(const modint rhs) const noexcept {
    return modint(*this) -= rhs;
  }
  constexpr modint operator*(const modint rhs) const noexcept {
    return modint(*this) *= rhs;
  }
  constexpr modint operator/(const modint rhs) const noexcept {
    return modint(*this) /= rhs;
  }
  constexpr modint &operator+=(const modint rhs) noexcept {
    a += rhs.a;
    if (a >= Modulus) {
      a -= Modulus;
    }
    return *this;
  }
  constexpr modint &operator-=(const modint rhs) noexcept {
    if (a < rhs.a) {
      a += Modulus;
    }
    a -= rhs.a;
    return *this;
  }
  constexpr modint &operator*=(const modint rhs) noexcept {
    a = a * rhs.a % Modulus;
    return *this;
  }
  constexpr modint &operator/=(modint rhs) noexcept {
    u64 exp = Modulus - 2;
    while (exp) {
      if (exp % 2) {
        *this *= rhs;
      }
      rhs *= rhs;
      exp /= 2;
    }
    return *this;
  }
};

/* template end */

using ll = long long;

template<typename Field,std::size_t ROW,std::size_t COLUMN>
class Mat{
  private:

  public:

  std::array<std::array<Field,COLUMN>,ROW> a;

  explicit Mat(const Field init=0){
    std::fill(a[0].begin(),a[ROW-1].end(),init);
  }

  Mat(const std::array<std::array<Field,COLUMN>,ROW>& a_):a(a_){}

  constexpr Field& operator()(std::size_t i,std::size_t j){return a[i][j];}
  constexpr static std::size_t get_row(){return ROW;}
  constexpr static std::size_t get_column(){return COLUMN;}
  constexpr bool operator==(const Mat rhs){
    for(std::size_t i=0;i<ROW;i++){
      for(std::size_t j=0;j<COLUMN;j++){
        if(a[i][j]!=rhs.a[i][j])return false;
      }
    }
    return true;
  }
  constexpr bool operator!=(const Mat rhs){return !(*this==rhs);}

  constexpr Mat operator+(const Mat rhs){
    return Mat(*this)+=rhs;
  }

  constexpr Mat operator-(const Mat rhs){
    return Mat(*this)-=rhs;
  }

  template<std::size_t NEWCOLUMN>
  constexpr Mat<Field,ROW,NEWCOLUMN> operator*(const Mat<Field,COLUMN,NEWCOLUMN> rhs){
    Mat<Field,ROW,NEWCOLUMN> tmp;
    for(std::size_t r=0;r<ROW;r++){
      for(std::size_t c=0;c<NEWCOLUMN;c++){
        for(std::size_t i=0;i<COLUMN;i++){
          tmp.a[r][c]+=a[r][i]*rhs.a[i][c];
        }
      }
    }
    return tmp;
  }

  constexpr Mat& operator+=(const Mat<Field,ROW,COLUMN> rhs){
    for(std::size_t i=0;i<ROW;i++){
      for(std::size_t j=0;j<COLUMN;j++){
        a[i][j]+=rhs.a[i][j];
      }
    }
    return *this;
  }

  constexpr Mat& operator-=(const Mat<Field,ROW,COLUMN> rhs){
    for(std::size_t i=0;i<ROW;i++){
      for(std::size_t j=0;j<COLUMN;j++){
        a[i][j]-=rhs.a[i][j];
      }
    }
    return *this;
  }

  constexpr Mat& operator*=(const Mat<Field,COLUMN,COLUMN> rhs){
    std::array<std::array<Field,COLUMN>,ROW> tmp;
    for(std::size_t r=0;r<ROW;r++){
      for(std::size_t c=0;c<COLUMN;c++){
        for(std::size_t i=0;i<COLUMN;i++){
          tmp[r][c]+=a[r][i]*rhs.a[i][c];
        }
      }
    }
    a=std::move(tmp);
    return *this;
  }

  constexpr static Mat id(){
    static_assert(ROW==COLUMN,"ROW must be equal to COLUMN");
    Mat<Field,ROW,COLUMN> temp;
    for(std::size_t i=0;i<ROW;i++)temp(i,i)=1;
    return temp;
  }

  //PA==LUとなる置換行列P,下三角L,上三角Uを求める 任意の正方行列に使える
  constexpr void LUPdecomposition(Mat& P,Mat& L,Mat& U){
    static_assert(ROW==COLUMN,"ROW must be equal to COLUMN");
    std::array<std::array<Field,COLUMN>,ROW> tmp=a;
    P=Mat::id();L=Mat(0);U=Mat(0);

    for(std::size_t i=0;i<ROW;i++){
      //ピボット選択
      for(std::size_t j=i;j<ROW;j++){
        Field val=0;
        for(std::size_t k=0;k<i;k++)val+=L.a[j][k]*U.a[k][i];
        if(val!=tmp[j][i]){
          std::swap(tmp[i],tmp[j]);
          std::swap(P.a[i],P.a[j]);
          std::swap(L.a[i],L.a[j]);
          break;
        }
      }

      L.a[i][i]=1;

      for(std::size_t j=i;j<ROW;j++){
        U.a[i][j]=tmp[i][j];
        for(std::size_t k=0;k<i;k++)U.a[i][j]-=L.a[i][k]*U.a[k][j];
      }

      if(U.a[i][i]!=0){
        for(std::size_t j=i+1;j<ROW;j++){
          L.a[j][i]=tmp[j][i];
          for(std::size_t k=0;k<i;k++)L.a[j][i]-=L.a[j][k]*U.a[k][i];
          L.a[j][i]/=U.a[i][i];
        }
      }
    }
  }

  constexpr Field det(){
    Mat p,l,u;
    LUPdecomposition(p,l,u);
    Field ans=1;
    for(std::size_t i=0;i<ROW;i++)ans*=u.a[i][i];
    return ans;
  }

  //A*ans=bとなるベクトルansを求める 解なしのときはfalseを返す
  constexpr bool linear_equation(Mat<Field,ROW,1> b,Mat<Field,ROW,1>& ans){
    Mat p,l,u;
    LUPdecomposition(p,l,u);

    b=p*b;
    
    for(std::size_t i=1;i<ROW;i++){
      for(std::size_t j=0;j<i;j++)b.a[i][0]-=l.a[i][j]*b.a[j][0];
    }

    //solve U*ans=b

    for(long long i=ROW-1;i>=0;i--){
      for(std::size_t j=i+1;j<ROW;j++)b.a[i][0]-=u.a[i][j]*b.a[j][0];
      if(b.a[i][0]!=0){
        if(u.a[i][i]==0)return false;
        b.a[i][0]/=u.a[i][i];
      }
    }
    ans=std::move(b);
    return true;
  }

  void show(){
    debug("show");
    std::cout<<"-------------------------------------\n";
    for(std::size_t i=0;i<ROW;i++){
      for(std::size_t j=0;j<COLUMN;j++){
        std::cout<<a[i][j]<<" ";
      }
      std::cout<<std::endl;
    }
  }
};

constexpr ll MOD=1e9+7;
using mint=modint<MOD>;

using mat=Mat<mint,6,6>;

int main() {
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);

  ll n;
  std::cin>>n;

  constexpr mint six=mint(1)/6;

  std::array<std::array<mint,6>,6> tmp{{{six,six,six,six,six,six},
           {1,0,0,0,0,0},
           {0,1,0,0,0,0},
           {0,0,1,0,0,0},
           {0,0,0,1,0,0},
           {0,0,0,0,1,0}}};

  mat pow(tmp);

  mat ret=mat::id();
  while(n>0){
    if(n&1)ret*=pow;
    pow*=pow;
    n>>=1;
  }

  std::cout<<ret(0,0).value()<<"\n";

  return 0;
}

yukicoder

結果

テストケース

ソースコード