結果

問題 No.2344 (l+r)^2
ユーザー 👑 p-adic
提出日時 2025-01-02 22:25:17
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 51 ms / 2,000 ms
コード長 20,237 bytes
コンパイル時間 2,798 ms
コンパイル使用メモリ 230,412 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2025-01-02 22:25:22
合計ジャッジ時間 3,766 ms
ジャッジサーバーID
(参考情報)
judge5 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define CERR( ANSWER ) cerr << ANSWER << endl;
#define LIBRARY_SEARCH if( LibrarySearch() != 0 ){ QUIT; };
#else
#pragma GCC optimize ( "O3" )
#pragma GCC optimize( "unroll-loops" )
#define CERR( ANSWER )
#define LIBRARY_SEARCH
#endif
#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
#define ATT __attribute__( ( target( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" ) ) )
#define TYPE_OF( VAR ) decay_t<decltype( VAR )>
#define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr )
#define CEXPR( LL , BOUND , VALUE ) constexpr LL BOUND = VALUE
#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 SET_ASSERT( A , MIN , MAX ) cin >> A; ASSERT( A , MIN , MAX )
#define GETLINE( A ) string A; getline( cin , A )
#define GETLINE_SEPARATE( A , SEPARATOR ) string A; getline( cin , A , SEPARATOR )
#define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( TYPE_OF( FINAL_PLUS_ONE ) VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ )
#define FOREQ( VAR , INITIAL , FINAL ) for( TYPE_OF( FINAL ) VAR = INITIAL ; VAR <= FINAL ; VAR ++ )
#define FOREQINV( VAR , INITIAL , FINAL ) for( TYPE_OF( INITIAL ) VAR = INITIAL ; VAR >= FINAL ; VAR -- )
#define FOR_ITR( ARRAY , ITR , END ) for( auto ITR = ARRAY .begin() , END = ARRAY .end() ; ITR != END ; ITR ++ )
#define REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT , 0 , HOW_MANY_TIMES )
#define QUIT return 0
#define COUT( ANSWER ) cout << ( ANSWER ) << "\n"
#define RETURN( ANSWER ) COUT( ANSWER ); QUIT
#define SET_PRECISION( PRECISION ) cout << fixed << setprecision( PRECISION )
#define DOUBLE( PRECISION , ANSWER ) SET_PRECISION << ( ANSWER ) << "\n"; QUIT
int QuitLibrarySearch( const int& problems_size ){
cerr << "" << problems_size - 1 << "";
CERR( "" );
CERR( "" );
return -1;
}
int LibrarySearch( int num = -1 )
{
vector<string> problems =
{
"" ,
"" ,
"" ,
"" ,
"" ,
"" ,
"" ,
"" ,
"" ,
"" ,
"" ,
""
};
int problems_size = problems.size();
string reply{};
if( num == -1 ){
CERR( "[y/n]" );
CIN( string , reply );
if( reply == "n" ){
CERR( "" );
CERR( "" );
return 0;
} else if( reply != "y" ){
CERR( "y/n" );
CERR( "" );
CERR( "" );
return -1;
}
CERR( "" );
CERR( "" );
CERR( "" );
FOR( i , 0 , problems_size ){
CERR( i << ": " << problems[i] );
}
cin >> num;
}
CEXPR( int , num_graph , 5 );
CEXPR( int , num_subsequence_sum , 6 );
CERR( "" );
int num_temp = 0;
if( num < 0 || num >= problems_size ){
return QuitLibrarySearch( problems_size );
} else if( num == num_temp++ ){
CERR( "[y/n/c]" );
cin >> reply;
CERR( "" );
if( reply == "y" ){
CERR( "OEIS" );
CERR( "https://oeis.org/?language=japanese" );
CERR( "" );
CERR( "" );
CERR( "- 調" );
CERR( "- p使" );
CERR( "- pp" );
CERR( " " );
CERR( "" );
} else if( reply == "n" ){
CERR( "" );
} else if( reply == "c" ){
CERR( "" );
CERR( "" );
return -1;
} else {
CERR( "y/n/c" );
CERR( "" );
CERR( "" );
return -1;
}
CERR( "" );
CERR( "" );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "" );
problems =
{
"" ,
"" ,
"" ,
"" ,
"" ,
};
problems_size = problems.size();
FOR( i , 0 , problems_size ){
CERR( i << ": " << problems[i] );
}
CIN( int , num );
CERR( "" );
num_temp = 0;
if( num < 0 || num >= problems_size ){
return QuitLibrarySearch( problems_size );
} else if( num == num_temp++ ){
CERR( "" );
CERR( "Mathematics\\SetTheory\\DirectProduct\\AffineSpace" );
} else if( num == num_temp++ ){
CERR( "XO(N)" );
CERR( "- O(N)X調X" );
CERR( "- XO(log_2 N)" );
CERR( " X" );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "" );
CERR( "- " );
CERR( " " );
CERR( "- " );
CERR( " " );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "gcdmax" );
CERR( "" );
} else {
return LibrarySearch( num = num_subsequence_sum );
}
} else if( num == num_temp++ ){
CERR( "" );
problems =
{
"" ,
"" ,
};
problems_size = problems.size();
FOR( i , 0 , problems_size ){
CERR( i << ": " << problems[i] );
}
CIN( int , num );
CERR( "" );
num_temp = 0;
if( num < 0 || num >= problems_size ){
return QuitLibrarySearch( problems_size );
} else if( num == num_temp++ ){
CERR( "" );
CERR( "- " );
CERR( "- " );
CERR( " - O(N)" );
CERR( " - O(N)" );
CERR( "- " );
CERR( "- Z" );
CERR( " https://qiita.com/Pro_ktmr/items/16904c9570aa0953bf05" );
CERR( "" );
} else {
CERR( "" );
CERR( "- O(N^2)" );
CERR( "- O(N^2)Manacher" );
CERR( " https://snuke.hatenablog.com/entry/2014/12/02/235837" );
CERR( "" );
}
} else if( num == num_temp++ ){
CERR( "" );
CERR( "" );
CERR( "O(N 2^N)" );
CERR( "" );
CERR( "" );
CERR( "- O(N^2)" );
CERR( "- O(N log_2 N)BIT" );
CERR( " \\Mathematics\\Combinatorial\\Permutation" );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace\\BIT" );
CERR( "" );
CERR( "" );
CERR( "" );
CERR( "i<j" );
CERR( "" );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "" );
problems =
{
"" ,
""
""
};
problems_size = problems.size();
FOR( i , 0 , problems_size ){
CERR( i << ": " << problems[i] );
}
CIN( int , num );
CERR( "" );
num_temp = 0;
if( num < 0 || num >= problems_size ){
return QuitLibrarySearch( problems_size );
} else if( num == num_temp++ ){
CERR( "" );
return LibrarySearch( num = num_graph );
} else if( num == num_temp++ ){
CERR( "" );
CERR( "- 調" );
CERR( "- " );
CERR( "- " );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "" );
CERR( "- O(HW)" );
CERR( "- O(HW)" );
CERR( "" );
CERR( "" );
CERR( "" );
CERR( "- " );
CERR( "- " );
CERR( "" );
}
} else if( num == num_temp++ ){
CERR( "" );
problems =
{
"" ,
"" ,
"" ,
""
};
problems_size = problems.size();
FOR( i , 0 , problems_size ){
CERR( i << ": " << problems[i] );
}
CIN( int , num );
CERR( "" );
num_temp = 0;
if( num < 0 || num >= problems_size ){
return QuitLibrarySearch( problems_size );
} else if( num == num_temp++ ){
CERR( "" );
CERR( "" );
CERR( "- BFSDijkstra" );
CERR( " \\Utility\\Search\\BreadthFirst" );
CERR( " \\Utility\\Search\\Dijkstra" );
CERR( "- " );
CERR( " - O(V^3)FloydWarshall" );
CERR( " \\Utility\\Search\\FloydWarshall" );
CERR( " - maxO(E(log_2 E + α(V)))UnionFind" );
CERR( " \\Utility\\VLTree\\UnionFindForest" );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "HeldKarp" );
} else if( num == num_temp++ ){
CERR( "" );
CERR( "\\Utility\\Search\\DepthFirst" );
CERR( "\\Utility\\VLTree" );
} else {
CERR( "- 0UnionFind" );
CERR( " \\Utility\\VLTree\\UnionFindForest" );
CERR( "- " );
CERR( " \\Utility\\Search\\DepthFirst" );
CERR( "- " );
CERR( "" );
}
} else if( num == num_temp++ ){
CERR( "" );
problems =
{
"" ,
""
};
problems_size = problems.size();
FOR( i , 0 , problems_size ){
CERR( i << ": " << problems[i] );
}
CIN( int , num );
CERR( "" );
num_temp = 0;
if( num < 0 || num >= problems_size ){
return QuitLibrarySearch( problems_size );
} else if( num == num_temp++ ){
CERR( "NWV" );
CERR( "- B=∞" );
CERR( "- B<∞O(2^N)" );
CERR( "- B<∞O(2^{N/2} N)" );
CERR( "- B<∞O(NV)[B-V,B+V]" );
CERR( " " );
CERR( " https://stackoverflow.com/a/18949218" );
CERR( "- W10^5O((N+W)log_2 W)" );
CERR( " " );
CERR( " \\Mathematics\\Polynomial" );
} else {
CERR( "NW" );
CERR( "- O(2^N)" );
CERR( "- O(2^N)" );
CERR( "- O(2^{N/2}N)" );
CERR( " " );
CERR( "- W10^5O((N+W)log_2 W)" );
CERR( " " );
CERR( " \\Mathematics\\Polynomial" );
}
CERR( "" );
} else if( num == num_temp++ ){
CERR( "使" );
} else if( num == num_temp++ ){
CERR( "" );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "" );
CERR( "- " );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace" );
CERR( "- UnionFind" );
CERR( " \\Utility\\VLTree\\UnionFindForest" );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "" );
problems =
{
"" ,
""
};
problems_size = problems.size();
FOR( i , 0 , problems_size ){
CERR( i << ": " << problems[i] );
}
CIN( int , num );
CERR( "" );
num_temp = 0;
if( num < 0 || num >= problems_size ){
return QuitLibrarySearch( problems_size );
} else if( num == num_temp++ ){
CERR( "" );
} else if( num == num_temp++ ){
CERR( "" );
return LibrarySearch( num = num_graph );
}
} else if( num == num_temp++ ){
CERR( "" );
problems =
{
"" ,
""
};
problems_size = problems.size();
FOR( i , 0 , problems_size ){
CERR( i << ": " << problems[i] );
}
CIN( int , num );
CERR( "" );
num_temp = 0;
if( num < 0 || num >= problems_size ){
return QuitLibrarySearch( problems_size );
} else if( num == num_temp++ ){
CERR( "NTK" );
CERR( "- O((N + T)log_2 K)" );
CERR( " \\Mathematics\\Function\\Iteration\\Doubling" );
CERR( "- O(TN)" );
CERR( " \\Mathematics\\Function\\Iteration\\LoopDetection" );
CERR( "" );
} else {
CERR( "" );
return LibrarySearch( num = num_graph );
}
}
CERR( "" );
CERR( "" );
CERR( "" );
return -1;
}
inline CEXPR( uint , bound_M , 30 );
class Mod
{
public:
uint m_val[bound_M + 1];
constexpr Mod() : m_val() { FOREQ( i , 0 , bound_M ){ m_val[i] = ( 1 << i ) - 1; } }
};
int main()
{
UNTIE;
LIBRARY_SEARCH;
CEXPR( uint , bound_T , 200000 );
CIN_ASSERT( T , 1 , bound_T );
CEXPR( uint , bound_N , 200000 ); // 05
// CEXPR( ll , bound_N , 1000000000 ); // 09
// CEXPR( ll , bound_N , 1000000000000000000 ); // 018
// CEXPR( int , bound_M , 100000 ); // 05
// CEXPR( ll , bound_M , 1000000000 ); // 09
// CEXPR( ll , bound_M , 1000000000000000000 ); // 018
static uint A[bound_N];
uint N;
uint N0;
uint M;
constexpr Mod mod{};
static uint v[bound_N + 1];
v[0] = 0;
FOREQ( i , 1 , bound_N ){
uint& vi = v[i];
vi = v[i-1];
uint i_copy = i;
while( ( i_copy & 1 ) == 0 ){
vi++;
i_copy >>= 1;
}
}
static uint c[bound_N + 1];
REPEAT( T ){
cin >> N >> M;
FOR( i , 0 , N ){
cin >> A[i];
}
if( N > M ){
N0 = N - M;
uint& vN0 = v[N0];
FOREQ( i , 1 , N0 ){
c[i] = vN0 > v[i] + v[N0 - i] ? 0 : 1;
}
FOR( i , 0 , M ){
uint& Ai = A[i];
FOREQ( j , 1 , N0 ){
Ai += c[j] * A[i+j];
}
}
N = M;
}
N0 = N - 1;
REPEAT( N0 ){
N--;
FOR( i , 0 , N ){
uint& Ai = A[i];
Ai *= Ai += A[i+1];
}
}
COUT( *A &= mod.m_val[M] );
}
QUIT;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0