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Ԁ�>
English