結果
| 問題 | No.1815 K色問題 |
| ユーザー |
👑  p-adic
|
| 提出日時 | 2022-06-24 22:43:06 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.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 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
13,636 KB |
| testcase_01 | AC | 1 ms
6,816 KB |
| testcase_02 | TLE | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
ソースコード
#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;
}