結果

問題 No.1815 K色問題
ユーザー 👑 p-adic
提出日時 2022-06-25 07:39:57
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 4,360 bytes
コンパイル時間 1,008 ms
コンパイル使用メモリ 76,672 KB
実行使用メモリ 818,176 KB
最終ジャッジ日時 2024-09-29 22:45:30
合計ジャッジ時間 2,474 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 3 MLE * 1 -- * 9
権限があれば一括ダウンロードができます

ソースコード

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;


}

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

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