#879578 (C++17) No.2344 (l+r)^2

提出ソース
結果

問題	No.2344 (l+r)^2
ユーザー	👑 p-adic
提出日時	2023-06-10 01:01:50
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	49 ms / 2,000 ms
コード長	20,298 bytes
コンパイル時間	3,644 ms
コンパイル使用メモリ	235,216 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-06-10 15:47:58
合計ジャッジ時間	4,620 ms
ジャッジサーバーID （参考情報）	judge1 / judge4
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	49 ms 6,944 KB
testcase_02	AC	11 ms 6,944 KB
testcase_03	AC	11 ms 6,940 KB
testcase_04	AC	12 ms 6,944 KB
testcase_05	AC	12 ms 6,940 KB
testcase_06	AC	12 ms 6,944 KB
testcase_07	AC	8 ms 6,944 KB
testcase_08	AC	9 ms 6,944 KB
testcase_09	AC	8 ms 6,940 KB
testcase_10	AC	10 ms 6,940 KB
testcase_11	AC	7 ms 6,944 KB
testcase_12	AC	26 ms 6,944 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#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" )
  #pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" )
  #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( "- 入力が素数に近い場合に規則性があれば、p進付値、p進法、" );
      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( "最大化すべき式に表れる項Xのうち、値の候補がO(N)個であるものを探しましょう。" );
      CERR( "- サブゴールの式がO(N)で計算できXに関して単調ならば、Xを決め打つ二分探索" );
      CERR( "- サブゴールの式がXを上手く並び替えるとO(log_2 N)で計算できるならば、" );
      CERR( "  優先度つきキューなどでのXの管理" );
      CERR( "を検討しましょう。" );
    } else if( num == num_temp++ ){
      CERR( "全順序か疎な半順序かで効率的な実装が違います。" );
      CERR( "- 全順序ならば、条件を満たす部分列の長さの最大値をインデックスに持つ配列を用いて、" );
      CERR( "  それらの部分列の末尾である項を記録すること" );
      CERR( "- 疎な半順序ならば、条件を満たす部分列の末尾をインデックスに持つ連想配列を用いて、" );
      CERR( "  それら部分列の長さの最大値を記録すること" );
      CERR( "を検討しましょう。" );
    } else if( num == num_temp++ ){
      CERR( "gcdやmaxなどの羃等演算に関する等式を指定した数え上げは不等式の方が" );
      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( "- 特定の２点のみを考える場合、BFSやDijkstra" );
      CERR( "  \\Utility\\Search\\BreadthFirst" );
      CERR( "  \\Utility\\Search\\Dijkstra" );
      CERR( "- 全ての２点の組み合わせを考える場合、" );
      CERR( "  - 一般のモノイド演算を考えておりO(V^3)が通りそうならば、FloydWarshall" );
      CERR( "    \\Utility\\Search\\FloydWarshall" );
      CERR( "  - max演算を考えておりO(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( "- 0次の連結性はUnionFind" );
      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( "項数N、重みの総和の上限W（多変数も可）、価値（和を取る値）の上限Vとします。" );
      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( "- Wが10^5オーダーで重みと価値が等しくO((N+W)log_2 W)が通りそうならば" );
      CERR( "  適当な法での畳み込み（確率的解法）" );
      CERR( "  \\Mathematics\\Polynomial" );
    } else {
      CERR( "項数N、重みの総和の上限Wとします。" );
      CERR( "- 重みと価値が異なりO(2^N)が通りそうならば愚直な２変数多項式乗算" );
      CERR( "- 重みと価値が等しくO(2^N)が通りそうならば愚直な１変数多項式乗算" );
      CERR( "- 重みと価値が等しくO(2^{N/2}N)が通りそうならば半分ずつ多項式乗算を" );
      CERR( "  して最後にそれらの積の１係数のみの計算" );
      CERR( "- 重みと価値が等しくWが10^5オーダーで法が与えられていてO((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( "定義域の要素数N、テストケース数T、反復回数の上限Kとします。" );
      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 ); // 0が5個
  // CEXPR( ll , bound_N , 1000000000 ); // 0が9個
  // CEXPR( ll , bound_N , 1000000000000000000 ); // 0が18個
  // CEXPR( int , bound_M , 100000 ); // 0が5個
  // CEXPR( ll , bound_M , 1000000000 ); // 0が9個
  // CEXPR( ll , bound_M , 1000000000000000000 ); // 0が18個
  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;
}
yukicoder

結果

テストケース

ソースコード
