結果

問題 No.1815 K色問題
ユーザー 👑 p-adicp-adic
提出日時 2022-06-25 08:01:05
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
MLE  
実行時間 -
コード長 3,968 bytes
コンパイル時間 3,429 ms
コンパイル使用メモリ 76,304 KB
実行使用メモリ 814,208 KB
最終ジャッジ日時 2024-09-29 22:45:38
合計ジャッジ時間 2,673 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 1 ms
6,816 KB
testcase_02 AC 2 ms
6,816 KB
testcase_03 AC 1 ms
6,820 KB
testcase_04 AC 2 ms
6,816 KB
testcase_05 AC 2 ms
6,816 KB
testcase_06 MLE -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <list>
#include <vector>
#include <string>
#include <stdio.h>
#include <stdint.h>
using namespace std;
using ull = unsigned long long;


#define P 1000000007 

ull S( const ull& N , const ull& M , const ull& K );

int main()
{

  ull N;
  ull M;
  ull K;

  cin >> N;
  cin >> M;
  cin >> K;

  cout << S( N , M , K ) << endl;
  return 0;

}

ull A1( const ull& M , const ull& K );
ull A2( const ull& M , const ull& K );
ull A3( const ull& M , const ull& K );
ull Comb( const ull& K , const ull& k );

ull S( const ull& N , const ull& M , const ull& K )
{

  if( K == 1 ){

    return 0;

  }

  static ull n = 0;
  static ull m = 0;
  static vector<ull> s{};

  if( n != N || m != M ){

    n = N;
    m = M;
    s.clear();
    s.push_back( 0 );
    s.push_back( 0 );

  } else if( K < s.size() ){

    return s[K];

  }

  ull a;
  
  if( N == 1 ){

    a = A1( M , K );

  } else if( N == 2 ){

    a = A2( M , K );

  } else {

    a = A3( M , K );

  }

  for( ull k = 2 ; k < K ; k++ ){

    ull s = ( S( N , M , k ) * Comb( K , k ) ) % P;

    if( a >= s ){

      a -= s;

    } else {

      a = ( a + ( P - s ) ) % P;

    }

  }

  while( s.size() < K ){

    s.push_back( 0 );

  }

  s.push_back( a );

  return a;
  
}

ull A1( const ull& M , const ull& K )
{

  // N == 1
  // A_M = K * ( K - 1 ) ^ { M - 1 }

    if( M == 1 ){
      
      return K;

    }

    return ( A1( M - 1 , K ) * ( K - 1 ) ) % P;

}

ull A2( const ull& M , const ull& K )
{

  // K < 2
  // A_M = 0

  if( K == 1 ){

    return 0;

  }

  // N == 2 && K >= 2
  // A_M
  // = K * ( K - 1 ) * ( ( K - 1 ) + ( K - 2 ) * ( K - 2 ) ) ^ { M - 1 }

  if( M == 1 ){

    return ( K * ( K - 1 ) ) % P;

  }

  static ull k = 0;
  static ull m = 0;

  if( k != K ){

    k = K;
    m = ( ( K - 1 ) + ( K - 2 ) * ( K - 2 ) ) % P;

  }
  
  return ( A2( M - 1 , K ) * m ) % P;


}

void BC( const ull& M , const ull& K , ull& b , ull& c );

ull A3( const ull& M , const ull& K )
{
  // N == 3
  // A_M = B_M + C_M

  ull b;
  ull c;
  BC( M , K , b , c );
  return ( b + c ) % P;

}

void BC( const ull& M , const ull& K , ull& b , ull& c )
{

  // B_1 = K * ( K - 1 )
  // C_1 = K * ( K - 1 ) * ( K - 2 )

  if( M == 1 ){

    b = ( K * ( K - 1 ) ) % P;

    if( K < 3 ){

      c = 0;

    } else {

      c = ( b * ( K - 2 ) ) % P;

    }

    return;

  }

  static ull k = 0;
  static ull m11 = 0;
  static ull m12 = 0;
  static ull m21 = 0;
  static ull m22 = 0;

  if( k != K ){

    k = K;
    m11 = ( ( ( K - 3 ) * K ) + 3 ) % P; 
    m12 = ( ( ( K - 3 ) * K ) + 5 - K ) % P;
    m21 = ( ( K - 2 ) * ( ( ( K - 3 ) * K + 5 - K ) % P ) ) % P; 
    m22 = ( 2 * ( ( ( K - 2 ) * ( K - 2 ) ) % P ) + ( ( K - 3 ) * ( ( ( K - 2 ) + ( K - 3 ) * ( K - 3 ) ) % P ) ) % P ) % P; 

  }
  
  ull b_prev;
  ull c_prev;
  BC( M - 1 , K , b_prev , c_prev );

  // B_{ M + 1 }
  // = B_M * ( ( K - 1 ) + ( K - 2 ) ^ 2 )
  //   + C_M * ( ( K - 1 ) + ( K - 3 ) * ( K - 2 ) )
  // = B_M * ( K ^ 2 - 3 * K + 3 )
  //   + C_M * ( K ^ 2 - 4 * K + 5 )
  // C_{ M + 1 }
  // = B_M * ( ( K - 2 ) + ( K - 2 ) * ( K - 3 ) + ( K - 2 ) * ( ( K - 2 ) + ( K - 3 ) ^ 2 ) )
  //   + C_M * ( ( K - 2 ) + ( K - 2 ) * ( K - 3 ) + ( K - 2 ) ^ 2 + ( K - 3 ) * ( ( K - 2 ) + ( K - 3 ) ^ 2 ) )
  // = B_M * ( ( K - 2 ) * ( K ^ 2 - 4 * K + 5 ) )
  //   + C_M * ( 2 * ( K - 2 ) ^ 2 + ( K - 3 ) * ( ( K - 2 ) + ( K - 3 ) ^ 2 ) )
  b = ( ( b_prev * m11 ) % P + ( c_prev * m12 ) % P ) % P;
  c = ( ( b_prev * m21 ) % P + ( c_prev * m22 ) % P ) % P;
  return;

}

ull Comb( const ull& K , const ull& k )
{

  if( k == 0 || k == K ){

    return 1;

  }

  if( K == 1 ){

    return 1;

  }

  static vector<vector<ull> > c{};

  while( c.size() <= K ){

    c.push_back( vector<ull>() );

  }

  vector<ull>& v = c[K];
  
  while( v.size() <= k ){

    v.push_back( 0 );

  }

  if( v[k] != 0 ){

    return v[k];

  }

  v[k] = ( Comb( K - 1 , k - 1 ) + Comb( K - 1 , k ) ) % P;
  return v[k];

}
0