• branch=trunk inherited from [9165bd3629]
• sym-trunk inherited from [9165bd3629]

Added SRM/566-U/1A.cpp version [1342371824ba4cfe]

            1  +#include <iostream>
            2  +#include <sstream>
            3  +#include <iomanip>
            4  +#include <vector>
            5  +#include <string>
            6  +#include <map>
            7  +#include <set>
            8  +#include <algorithm>
            9  +#include <numeric>
           10  +#include <iterator>
           11  +#include <functional>
           12  +#include <complex>
           13  +#include <queue>
           14  +#include <stack>
           15  +#include <cmath>
           16  +#include <cassert>
           17  +using namespace std;
           18  +typedef long long LL;
           19  +typedef long double LD;
           20  +typedef complex<LD> CMP;
           21  +
           22  +LL comb(LL n, LL k)
           23  +{
           24  + k = min(k, n-k);
           25  +
           26  + LL c = 1;
           27  + for(LL i=0; i<k; ++i)
           28  +  c *= n-i, c /= i+1;
           29  + return c;
           30  +}
           31  +
           32  +class PenguinSledding { public:
           33  + long long countDesigns(int numCheckpoints, vector <int> checkpoint1, vector <int> checkpoint2)
           34  + {
           35  +  LL zero = 1;
           36  +  LL one = checkpoint1.size();
           37  +  LL star = 0;
           38  +  LL triangle = 0;
           39  +
           40  +  for(int center=1; center<=numCheckpoints; ++center) {
           41  +   int leaf = 0;
           42  +   for(int i=0; i<checkpoint1.size(); ++i)
           43  +    if(checkpoint1[i] == center)
           44  +     ++leaf;
           45  +    else if(checkpoint2[i] == center)
           46  +     ++leaf;
           47  +   for(int k=2; k<=leaf; ++k)
           48  +    star += comb(leaf, k);
           49  +  }
           50  +
           51  +  set< pair<int,int> > conn;
           52  +  for(int i=0; i<checkpoint1.size(); ++i) {
           53  +   conn.insert(make_pair(checkpoint1[i], checkpoint2[i]));
           54  +   conn.insert(make_pair(checkpoint2[i], checkpoint1[i]));
           55  +  }
           56  +  for(int a=1; a<=numCheckpoints; ++a)
           57  +  for(int b=a+1; b<=numCheckpoints; ++b)
           58  +  for(int c=b+1; c<=numCheckpoints; ++c)
           59  +   if(conn.count(make_pair(a,b)) && conn.count(make_pair(b,c)) && conn.count(make_pair(c,a)))
           60  +    ++triangle;
           61  +
           62  +  return zero + one + star + triangle;
           63  + }
           64  +};
           65  +
           66  +// BEGIN CUT HERE
           67  +#include <ctime>
           68  +double start_time; string timer()
           69  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           70  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           71  + { os << "{ ";
           72  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           73  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           74  +void verify_case(const long long& Expected, const long long& Received) {
           75  + bool ok = (Expected == Received);
           76  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           77  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           78  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           79  +#define END  verify_case(_, PenguinSledding().countDesigns(numCheckpoints, checkpoint1, checkpoint2));}
           80  +int main(){
           81  +
           82  +CASE(0)
           83  + int numCheckpoints = 2;
           84  + int checkpoint1_[] = {1};
           85  +   vector <int> checkpoint1(checkpoint1_, checkpoint1_+sizeof(checkpoint1_)/sizeof(*checkpoint1_));
           86  + int checkpoint2_[] = {2};
           87  +   vector <int> checkpoint2(checkpoint2_, checkpoint2_+sizeof(checkpoint2_)/sizeof(*checkpoint2_));
           88  + long long _ = 2LL;
           89  +END
           90  +CASE(1)
           91  + int numCheckpoints = 4;
           92  + int checkpoint1_[] = {1,2,3};
           93  +   vector <int> checkpoint1(checkpoint1_, checkpoint1_+sizeof(checkpoint1_)/sizeof(*checkpoint1_));
           94  + int checkpoint2_[] = {2,3,4};
           95  +   vector <int> checkpoint2(checkpoint2_, checkpoint2_+sizeof(checkpoint2_)/sizeof(*checkpoint2_));
           96  + long long _ = 6LL;
           97  +END
           98  +CASE(2)
           99  + int numCheckpoints = 6;
          100  + int checkpoint1_[] = {1,3,6};
          101  +   vector <int> checkpoint1(checkpoint1_, checkpoint1_+sizeof(checkpoint1_)/sizeof(*checkpoint1_));
          102  + int checkpoint2_[] = {2,4,4};
          103  +   vector <int> checkpoint2(checkpoint2_, checkpoint2_+sizeof(checkpoint2_)/sizeof(*checkpoint2_));
          104  + long long _ = 5LL;
          105  +END
          106  +CASE(3)
          107  + int numCheckpoints = 50;
          108  + int checkpoint1_[] = {40, 40, 40, 40, 40, 40, 40, 40,
          109  + 40, 40, 40, 40, 50, 40, 40, 40,
          110  + 23, 4, 24, 40, 22, 40, 8, 40, 40,
          111  + 40, 34, 21, 40, 40, 38, 40, 40,
          112  + 40, 40, 40, 28, 40, 40, 40, 40,
          113  + 46, 13, 40, 40, 40, 47, 40, 40};
          114  +   vector <int> checkpoint1(checkpoint1_, checkpoint1_+sizeof(checkpoint1_)/sizeof(*checkpoint1_));
          115  + int checkpoint2_[] = {45, 42, 20, 48, 12, 32, 25, 10,
          116  + 26, 39, 16, 2, 19, 43, 37, 17,
          117  + 19, 19, 19, 18, 19, 27, 19, 29,
          118  + 11, 36, 19, 19, 1, 41, 19, 35,
          119  + 14, 33, 49, 3, 19, 7, 5, 19, 31,
          120  + 19, 19, 6, 9, 15, 19, 44, 30};
          121  +   vector <int> checkpoint2(checkpoint2_, checkpoint2_+sizeof(checkpoint2_)/sizeof(*checkpoint2_));
          122  + long long _ = 68719493118LL;
          123  +END
          124  +CASE(4)
          125  + int numCheckpoints = 36;
          126  + int checkpoint1_[] = {13, 24, 24, 20, 31, 16, 10, 36, 34, 32,
          127  + 28, 5, 20, 29, 23, 2, 14, 4, 9, 5, 19,
          128  + 21, 8, 1, 26, 27, 25, 15, 22, 30, 30,
          129  + 6, 11, 7, 2, 35, 13, 29, 4, 12, 33, 18,
          130  + 13, 14, 17, 35, 3};
          131  +   vector <int> checkpoint1(checkpoint1_, checkpoint1_+sizeof(checkpoint1_)/sizeof(*checkpoint1_));
          132  + int checkpoint2_[] = {10, 15, 27, 1, 29, 11, 5, 18, 33, 1, 9,
          133  + 2, 31, 6, 19, 10, 33, 18, 6, 27, 3, 22,
          134  + 4, 12, 31, 30, 34, 16, 7, 24, 3, 28, 15,
          135  + 21, 22, 8, 26, 20, 14, 32, 25, 17, 35,
          136  + 8, 36, 26, 23};
          137  +   vector <int> checkpoint2(checkpoint2_, checkpoint2_+sizeof(checkpoint2_)/sizeof(*checkpoint2_));
          138  + long long _ = 162LL;
          139  +END
          140  +/*
          141  +CASE(5)
          142  + int numCheckpoints = ;
          143  + int checkpoint1_[] = ;
          144  +   vector <int> checkpoint1(checkpoint1_, checkpoint1_+sizeof(checkpoint1_)/sizeof(*checkpoint1_));
          145  + int checkpoint2_[] = ;
          146  +   vector <int> checkpoint2(checkpoint2_, checkpoint2_+sizeof(checkpoint2_)/sizeof(*checkpoint2_));
          147  + long long _ = LL;
          148  +END
          149  +CASE(6)
          150  + int numCheckpoints = ;
          151  + int checkpoint1_[] = ;
          152  +   vector <int> checkpoint1(checkpoint1_, checkpoint1_+sizeof(checkpoint1_)/sizeof(*checkpoint1_));
          153  + int checkpoint2_[] = ;
          154  +   vector <int> checkpoint2(checkpoint2_, checkpoint2_+sizeof(checkpoint2_)/sizeof(*checkpoint2_));
          155  + long long _ = LL;
          156  +END
          157  +*/
          158  +}
          159  +// END CUT HERE

Added SRM/566-U/1B.cpp version [770f87bd162c875d]

            1  +#include <iostream>
            2  +#include <sstream>
            3  +#include <iomanip>
            4  +#include <vector>
            5  +#include <string>
            6  +#include <map>
            7  +#include <set>
            8  +#include <algorithm>
            9  +#include <numeric>
           10  +#include <iterator>
           11  +#include <functional>
           12  +#include <complex>
           13  +#include <queue>
           14  +#include <stack>
           15  +#include <cmath>
           16  +#include <cassert>
           17  +using namespace std;
           18  +typedef long long LL;
           19  +typedef long double LD;
           20  +typedef complex<LD> CMP;
           21  +
           22  +static const unsigned MODVAL = 1000000007;
           23  +struct mint
           24  +{
           25  + unsigned val;
           26  + mint():val(0){}
           27  + mint(int      x):val(x%MODVAL) {}
           28  + mint(unsigned x):val(x%MODVAL) {}
           29  + mint(LL       x):val(x%MODVAL) {}
           30  +};
           31  +mint& operator+=(mint& x, mint y) { return x = x.val+y.val; }
           32  +mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; }
           33  +mint operator+(mint x, mint y) { return x+=y; }
           34  +mint operator*(mint x, mint y) { return x*=y; }
           35  +
           36  +template<typename T>
           37  +vector<T> MATMULxx(const vector<T>& a, const vector<T>& v)
           38  +{
           39  + int N = a.size();
           40  + vector<T> u(N);
           41  + for(int i=0; i<N; ++i)
           42  + for(int j=0; j<N; ++j)
           43  +  u[i] += a[(j-i+N)%N]*v[j];
           44  + return u;
           45  +}
           46  +
           47  +template<typename T>
           48  +vector<T> MATMULxx(const vector<T>& a)
           49  +{
           50  + int N = a.size();
           51  + vector<T> c(N);
           52  + for(int j=0; j<N; ++j)
           53  + for(int k=0; k<N; ++k)
           54  +  c[j] += a[k]*a[(j-k+N)%N];
           55  + return c;
           56  +}
           57  +
           58  +template<typename T>
           59  +vector<T> MATPOWMULxx(vector<T> a, LL e, vector<T> v)
           60  +{
           61  + for(; e; e>>=1, a=MATMULxx(a))
           62  +  if(e&1)
           63  +   v = MATMULxx(a, v);
           64  + return v;
           65  +}
           66  +
           67  +class PenguinEmperor { public:
           68  + int countJourneys(int N, long long daysPassed)
           69  + {
           70  +  vector<mint> v(N), u(N);
           71  +  u[0] = 1;
           72  +  for(int i=0; i<N; ++i) {
           73  +   if(i == daysPassed % N)
           74  +    v = u;
           75  +   vector<mint> uu(N);
           76  +   for(int x=0; x<N; ++x) {
           77  +    int f = (x+i+1)%N;
           78  +    int b = (x-i-1+N)%N;
           79  +    uu[x] += u[f];
           80  +    if(f!=b)
           81  +     uu[x] += u[b];
           82  +   }
           83  +   u = uu;
           84  +  }
           85  +
           86  +  v = MATPOWMULxx(u, daysPassed/N, v);
           87  +  return v[0].val;
           88  + }
           89  +};
           90  +
           91  +// BEGIN CUT HERE
           92  +#include <ctime>
           93  +double start_time; string timer()
           94  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           95  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           96  + { os << "{ ";
           97  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           98  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           99  +void verify_case(const int& Expected, const int& Received) {
          100  + bool ok = (Expected == Received);
          101  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          102  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          103  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          104  +#define END  verify_case(_, PenguinEmperor().countJourneys(numCities, daysPassed));}
          105  +int main(){
          106  +
          107  +CASE(0)
          108  + int numCities = 3;
          109  + long long daysPassed = 2LL;
          110  + int _ = 2;
          111  +END
          112  +CASE(1)
          113  + int numCities = 4;
          114  + long long daysPassed = 3LL;
          115  + int _ = 2;
          116  +END
          117  +CASE(2)
          118  + int numCities = 5;
          119  + long long daysPassed = 36LL;
          120  + int _ = 107374182;
          121  +END
          122  +CASE(3)
          123  + int numCities = 300;
          124  + long long daysPassed = 751LL;
          125  + int _ = 413521250;
          126  +END
          127  +CASE(4)
          128  + int numCities = 300;
          129  + long long daysPassed = 750LL;
          130  + int _ = 0;
          131  +END
          132  +CASE(5)
          133  + int numCities = 350;
          134  + long long daysPassed = 1000000000000000000LL;
          135  + int _ = 667009739;
          136  +END
          137  +CASE(6)
          138  + int numCities = 5;
          139  + long long daysPassed = 7LL;
          140  + int _ = 12;
          141  +END
          142  +/*
          143  +CASE(7)
          144  + int numCities = ;
          145  + long long daysPassed = LL;
          146  + int _ = ;
          147  +END
          148  +CASE(8)
          149  + int numCities = ;
          150  + long long daysPassed = LL;
          151  + int _ = ;
          152  +END
          153  +*/
          154  +}
          155  +// END CUT HERE

Modified lib/doc/nim.txt from [afa6596dc04e5d36] to [a6c762d68e00b3ce].

    56     56   -------------------------------------------------------------------------------------------
    57     57   定理【ゲームの和はxor】
    58     58     - *n1 + *n2 = *(n1 xor n2)
    59     59     - より一般的に G1≡*n1, G2≡*n2 ならば、G1 + G2 ≡ *(n1 xor n2)
    60     60   
    61     61     証明
    62     62       - *n1 + *n2 + *(n1 xor n2) が必敗であることを言えば良い。
    63         -
           63  +    - (n1 xor n2 xor (n1 xor n2)) は 0 である
           64  +    - 一手動かすと 0 じゃなくなる
           65  +        >> n1 と n2 と n1^n2 のどれか一個だけビットが変わるので絶対xorが変わるから
           66  +    - 相手は一手動かして 0 に戻せる
           67  +        >> 常に
           68  +    - よって最終局面"全部 0"になるのは絶対に自分のターン
    64     69   
    65     70   
    66     71   -------------------------------------------------------------------------------------------
    67     72   定理【ゲームの状態遷移はmex】
    68     73     - {*n1, ..., *nk} ≡ *mex(n1,...,nk)
    69     74         where mex(S) = min(nat \setminus S)
    70     75