結果
| 問題 |
No.1815 K色問題
|
| ユーザー |
👑  p-adic
|
| 提出日時 | 2022-06-25 08:01:05 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.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 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 3 MLE * 1 -- * 9 |
ソースコード
#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];
}