結果
問題 |
No.2113 Distance Sequence 1.5
|
ユーザー |
👑 |
提出日時 | 2022-10-29 01:45:03 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,912 bytes |
コンパイル時間 | 1,707 ms |
コンパイル使用メモリ | 192,648 KB |
最終ジャッジ日時 | 2025-02-08 15:36:33 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 21 |
ソースコード
#include<bits/stdc++.h> using namespace std; using ll = long long; #define TYPE_OF( VAR ) remove_const<remove_reference<decltype( VAR )>::type >::type #define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr ) #define CIN( LL , A ) LL A; cin >> A #define ASSERT( A , MIN , MAX ) assert( MIN <= A && A <= MAX ) #define CIN_ASSERT( A , MIN , MAX ) CIN( TYPE_OF( MAX ) , A ); ASSERT( A , MIN , MAX ) #define QUIT return 0 #define RETURN( ANSWER ) cout << ( ANSWER ) << "\n"; QUIT #define POWER( ANSWER , ARGUMENT , EXPONENT , MODULO ) \ TYPE_OF( ARGUMENT ) ANSWER = 1; \ { \ TYPE_OF( ARGUMENT ) ARGUMENT_FOR_SQUARE_FOR_POWER = ( ARGUMENT ); \ TYPE_OF( EXPONENT ) EXPONENT_FOR_SQUARE_FOR_POWER = ( EXPONENT ); \ while( EXPONENT_FOR_SQUARE_FOR_POWER != 0 ){ \ if( EXPONENT_FOR_SQUARE_FOR_POWER % 2 == 1 ){ \ ANSWER = ( ANSWER * ARGUMENT_FOR_SQUARE_FOR_POWER ) % MODULO; \ } \ ARGUMENT_FOR_SQUARE_FOR_POWER = ( ARGUMENT_FOR_SQUARE_FOR_POWER * ARGUMENT_FOR_SQUARE_FOR_POWER ) % MODULO; \ EXPONENT_FOR_SQUARE_FOR_POWER /= 2; \ } \ } \ int main() { UNTIE; constexpr const ll P = 998244353; constexpr const ll bound = 1000000000000000000; CIN_ASSERT( N , 1 , bound ); CIN_ASSERT( M , 1 , bound ); CIN_ASSERT( K , 1 , bound ); // c[n,m,k] := (1からmまでの整数からなる長さnの列でmax - min < kであるものの総数) // = max( 0 , m - k ) * ( k ^ n - ( k - 1 ) ^ n ) + min( m , k ) ^ n // = m > k ? ( m - k + 1 ) * k ^ n - ( m - k ) * ( k - 1 ) ^ n : m ^ n N = ( N * 2 ) % ( P - 1 ); if( M <= K ){ M %= P; POWER( answer , M , N , P ); RETURN( answer ); } M = ( M - K ) % P; K %= P; POWER( K_power , K , N , P ); POWER( K_minus_power , K == 0 ? P - 1 : K - 1 , N , P ); RETURN( ( ( M + 1 ) * K_power + P - ( ( M * K_minus_power ) % P ) ) % P ); }