結果

問題 No.1815 K色問題
ユーザー 👑 p-adic
提出日時 2022-06-24 22:43:06
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,828 bytes
コンパイル時間 813 ms
コンパイル使用メモリ 71,352 KB
実行使用メモリ 13,636 KB
最終ジャッジ日時 2024-09-29 22:45:09
合計ジャッジ時間 4,245 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 TLE * 1
other -- * 13
権限があれば一括ダウンロードができます

ソースコード

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();

  } 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;

    }

  }

  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 )

  if( M == 1 ){

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

  }

  static ull k = 0;
  static ull m1 = 0;
  static ull m2 = 0;

  if( k != K ){

    k = K;
    m1 = ( ( ( K - 3 ) * K ) + 3 ) % P; 
    m2 = ( ( ( K - 3 ) * K ) + 5 - K ) % P; 

  }

  return ( ( B( M - 1 , K ) * m1 ) % P + ( C( M - 1 , K ) * m2 ) % P ) % P;

}

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 ) )

  if( M == 1 ){

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

  }

  static ull k = 0;
  static ull m1 = 0;
  static ull m2 = 0;

  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; 

  }

  return ( ( B( M - 1 , K ) * m1 ) % P + ( C( M - 1 , K ) * m2 ) % P ) % P;
  
}

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

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

    return 1;

  }

  if( K == 1 ){

    return 1;

  }
  
  return ( Comb( K - 1 , k - 1) + Comb( K - 1 , k ) ) % P;

}
0