Niestety, nie byliśmy w stanie w pełni poprawnie wyświetlić tego pliku, ponieważ nie jest zakodowany w UTF-8.
Możesz pobrać ten plik i spróbować otworzyć go samodzielnie.
//~ while (clock()<=69*CLOCKS_PER_SEC) //~ #pragma comment(linker, "/stack:200000000") #pragma GCC optimize("O3") //~ #pragma GCC optimize("Ofast") //~ #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") //~ #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; using namespace std; template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #define sim template < class c #define ris return * this #define dor > debug & operator << #define eni(x) sim > typename \ enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) { sim > struct rge { c b, e; }; sim > rge<c> range(c i, c j) { return rge<c>{i, j}; } sim > auto dud(c* x) -> decltype(cerr << *x, 0); sim > char dud(...); struct debug { #ifdef LOCAL ~debug() { cerr << endl; } eni(!=) cerr << boolalpha << i; ris; } eni(==) ris << range(begin(i), end(i)); } sim, class b dor(pair < b, c > d) { ris << "(" << d.first << ", " << d.second << ")"; } sim dor(rge<c> d) { *this << "["; for (auto it = d.b; it != d.e; ++it) *this << ", " + 2 * (it == d.b) << *it; ris << "]"; } #else sim dor(const c&) { ris; } #endif }; #define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] " #define shandom_ruffle random_shuffle using ll=long long; using pii=pair<int,int>; using pll=pair<ll,ll>; using vi=vector<int>; using vll=vector<ll>; const int nax=6507; using typ=unsigned int; using wielo=vector<typ>; using macierz=vector<wielo>; vi granice{1, 5, 13, 17, 25, 29, 37, 41, 53, 61, 65, 73, 85, 89, 97, 101, 109, 113, 125, 137, 145, 149, 157, 169, 173, 181, 185, 193, 197, 205, 221, 229, 233, 241}; wielo pamA{4, 80, 1840, 133104, 11993264, 1535638064, 547682336, 3565658176, 3296100608, 2140219456, 3385992320, 3842663392, 3551711264, 1690965744, 1096062416, 1654252048, 3840732912, 2907057520, 3469017776, 2032222640, 3515497840, 3013762768, 2523529024, 319093744, 2341737680, 3827362848, 3184172144, 1483982160, 2372749376, 1914047168, 4248956880, 902879568, 3805621776, 1039347088}; wielo pamB{2, 600, 45080, 6322440, 941471224, 3120122216, 994795728, 1747674592, 1737252992, 609748448, 3699520960, 437713712, 211046672, 3278960776, 3536563560, 698669816, 2058972184, 1625953512, 1413602936, 729910696, 2923764040, 2423879112, 1924361824, 846443928, 3098352536, 1786450640, 896232760, 554890456, 3415863712, 1075281376, 1886138696, 1278219224, 4080257288, 1409074904}; wielo pamC{1, 5364, 1214476, 316485372, 3422118060, 4129614348, 2775644744, 2045614896, 3727894528, 425738640, 3239764672, 1455255704, 1566340968, 60455484, 2044986516, 3324211460, 1791125852, 2391785180, 473759820, 1424893676, 2882541564, 855010996, 3401054960, 267485404, 1817452788, 1617598184, 1284907484, 378187892, 1215312240, 2574093040, 3416402068, 1422492212, 856427012, 396331812}; ll limx, limy; typ typx, typy; int k; int sx, sy; vector <pii> wek; typ dp[nax][nax]; //brutero const int vax=2401; vi rzo[nax]; vi kol[nax]; typ ter[vax][vax]; typ brut() { for (int i=0; i<=min((ll)sx, max(limx, limy)-1); i++) for (int j=0; j<=min((ll)sy, max(limx, limy)-1); j++) if (dp[i][j]) { rzo[i].push_back(j); kol[j].push_back(i); } typ ret=0; for (int i=0; i<=sy+sx && i<limy; i++) { for (int j=0; j<=min(sx+sy, vax-1); j++) for (int l=0; l<=min(sx+sy, vax-1); l++) ter[j][l]=0; for (int j=0; j<=i; j++) { int l=i-j; if (j>sy || l>sx) continue; for (int a : kol[j]) for (int b : rzo[l]) ter[a][b]+=dp[a][j]*dp[l][b]; } for (int r=-min((ll)sy, limx); r<=min((ll)sx, limx); r++) { for (int a1=0; a1<=min((ll)sx, limx); a1++) { if (a1-r<0 || a1-r>min((ll)sy, limx)) continue; for (int a2=0; a2<=min((ll)sx, limx); a2++) { if (a2-r<0 || a2-r>min((ll)sy, limx)) continue; int b1=a1-r; int b2=a2-r; if (a1+b2>=limx) continue; ret+=(typy-(typ)i)*(typx-(typ)a1-(typ)b2)*ter[a1][b1]*ter[a2][b2]; } } } } ret-=typx*typy; for (auto i : wek) if ((ll)i.first<limx && (ll)i.second<limy) ret-=(typx-i.first)*(typy-i.second); for (auto i : wek) if ((ll)i.first<limy && (ll)i.second<limx) ret-=(typy-i.first)*(typx-i.second); return ret; } typ toout[vax][vax]; struct Compress { static unsigned char data[]; // Wersja bez UTF-8 używa 8/8 bitów. int pos = -1, left = 1; // Wersja z UTF-8 używa 16/24 = 2/3 bitów. uint64_t Data(int bits, uint64_t x = 0) { assert(1 <= bits and bits <= 64); for (int i = 0; i < bits; i++) { if (left-- == 1) { pos++; left = 7; // Jeśli nie UTF-8. } if (((x >> i) ^ (data[pos] >> left)) & 1) { data[pos] ^= 1 << left; x ^= 1llu << i; } } return x; } void Print() { constexpr char code[] = "KaMylMaDoWnA"; // Length must be <= 16. std::ofstream out("compress.cpp"); out << "unsigned char Compress::data[] = R\"" << code << "("; out.write(reinterpret_cast<const char*>(data), pos + 1); out << ")" << code << "\";\n"; } }; Compress pawel; void get_prepro() { for (int i=2000; i<=2194; i++) for (int j=2000; j<=i; j++) toout[i][j]=toout[j][i]=pawel.Data(32); for (int i=2000; i<2193; i++) for (int j=2195; j<=2400; j++) toout[i][j]=toout[j][i]=toout[i][j-1]*2-toout[i][j-2]; } int main() { scanf("%lld%lld%d", &limx, &limy, &k); get_prepro(); typx=limx; typy=limy; for (int i=1; i<=k; i++) { for (int j=0; j<=k; j++) { if (__gcd(i, j)!=1) continue; int w=i*i+j*j; int x=0; while(x*x<w) x++; if (x*x==w && x<=k) wek.push_back({i, j}); } } dp[0][0]=1; for (auto i : wek) { for (int j=sx; j>=0; j--) for (int l=sy; l>=0; l--) dp[j+i.first][l+i.second]+=dp[j][l]; sx+=i.first; sy+=i.second; } //~ debug() << imie(sx) << " " << imie(sy); if (k<=15 || (limx<=150 && limy<=150)) { printf("%u\n", brut()); return 0; } typ A=0; typ B=0; typ C=0; for (int i=0; i<(int)granice.size(); i++) { if (granice[i]<=k) { A=pamA[i]; B=pamB[i]; C=pamC[i]; } } if (min(limx, limy)>=sx+sy) { typ ret=A*typx*typy-B*(typx+typy)+C; ret-=typx*typy; for (auto i : wek) if (i.first<limx && i.second<limy) ret-=(typx-(typ)i.first)*(typy-(typ)i.second); for (auto i : wek) if (i.first<limy && i.second<limx) ret-=(typy-(typ)i.first)*(typx-(typ)i.second); printf("%u\n", ret); return 0; } assert(k>=97 && k<=100); typ ret=toout[limx][limy]; ret-=typx*typy; for (auto i : wek) if (i.first<limx && i.second<limy) ret-=(typx-(typ)i.first)*(typy-(typ)i.second); for (auto i : wek) if (i.first<limy && i.second<limx) ret-=(typy-(typ)i.first)*(typx-(typ)i.second); printf("%u\n", ret); return 0; } unsigned char Compress::data[] = R"KaMylMaDoWnA(b``�Ќ$��؊�jDʌ^ʴ�8���ZP�.��\�P��<~��^\��.�X��Ʀ��hZ0�l&px��J�"V�R�.6�lҾ0��p��$���2�fln(��d���VJ|���v�$����4�� ���nv`�P���ܬ Έ�����8�0���� �����D��Ξ�lԤ�Z@:X��L���Xp�b��2�lp�.�n�ʶjJ֢�<H� ~���P��~8Txx0bR�� ��p�j��������p���|H:"֢b8����x���ƒ��P�����*�а�P�zθb��t�V��@D8��.>���rdp��t$��h���l^r�L�<"�����pdr�"����rH��D4�P6�`0nnn��NVR�<����&Dj�� ʠ�TԀ�>