結果

問題 No.1815 K色問題
ユーザー 👑 p-adicp-adic
提出日時 2022-06-25 02:18:02
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 4,487 bytes
コンパイル時間 840 ms
コンパイル使用メモリ 79,000 KB
実行使用メモリ 814,720 KB
最終ジャッジ日時 2024-03-13 11:33:05
合計ジャッジ時間 2,663 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,676 KB
testcase_01 AC 2 ms
6,676 KB
testcase_02 AC 2 ms
6,676 KB
testcase_03 AC 2 ms
6,676 KB
testcase_04 WA -
testcase_05 AC 3 ms
6,676 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 uint = unsigned int;
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 );
uint 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 ) * (ull)( 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 - 1 ) * ( K - 2 ) ) ^ { M - 1 }
  // = K * ( K - 1 ) * ( K - 1 ) ^ { 2 * ( M - 1 ) }
  // = K * ( K - 1 ) ^ { 3 * ( M - 1 ) }

  if( M == 1 ){

    return K;

  }

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

  if( k != K ){

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

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


}

ull B( const ull& M , const ull& K );
ull C( const ull& M , const ull& K );

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

  return ( B( M , K ) + C( M , K ) ) % P;

}

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

  // K < 2
  // A_M = 0

  if( K == 1 ){

    return 0;

  }
  
  // B_1 = K * ( K - 1 )
  // 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 )

  static ull k = 0;
  static ull m1 = 0;
  static ull m2 = 0;
  static vector<ull> s{};

  if( k != K ){

    k = K;
    m1 = ( ( ( K - 3 ) * K ) + 3 ) % P; 
    m2 = ( ( ( K - 3 ) * K ) + 5 - K ) % P;
    s.clear();
    s.push_back( 0 );
    s.push_back( ( K * ( K - 1 ) ) % P );

  }

  if( M < s.size() ){

    return s[M];

  }

  ull a = ( ( B( M - 1 , K ) * m1 ) % P + ( C( M - 1 , K ) * m2 ) % P ) % P;
  s.push_back( a );
  return a;

}

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

  // K < 3
  // A_M = 0

  if( K < 3 ){

    return 0;

  }
  
  // C_1 = K * ( K - 1 ) * ( K - 2 )
  // 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 ) )

  static ull k = 0;
  static ull m1 = 0;
  static ull m2 = 0;
  static vector<ull> s{};

  if( k != K ){

    k = K;
    m1 = ( ( K - 2 ) * ( ( ( K - 3 ) * K + 5 - K ) % P ) ) % P; 
    m2 = ( 2 * ( ( ( K - 2 ) * ( K - 2 ) ) % P ) + ( ( K - 3 ) * ( ( ( K - 2 ) + ( K - 3 ) * ( K - 3 ) ) % P ) ) % P ) % P; 
    s.clear();
    s.push_back( 0 );
    s.push_back( ( ( ( K * ( K - 1 ) ) % P ) * ( K - 2 ) ) % P );

  }

  if( M < s.size() ){

    return s[M];

  }

  ull a = ( ( B( M - 1 , K ) * m1 ) % P + ( C( M - 1 , K ) * m2 ) % P ) % P;
  s.push_back( a );  
  return a;
  
}

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

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

    return 1;

  }

  if( K == 1 ){

    return 1;

  }

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

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

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

  }

  vector<uint>& 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