考试时发现那场已经考过了，于是开始倒着考。
考场上顺序开题。
\(\mathrm{A.}\mathbb{Exhibit}\)：\(\mathrm{dp}\)
\(\mathrm{B.}\mathbb{国家宝藏}\)：\(\mathrm{bfs}\)
\(\mathrm{C.}\mathbb{Lcm}\)：数学？
觉得 \(\mathrm{A}\) 好像在哪见过，前两题都比较水，于是直接莽 \(\mathrm{C}\)。
先打了个暴力，发现只能跑到 \(32\) 左右，于是果断想正解。
大约推了一个小时，发现可以根据限制最小公倍数的质因子的范围来进行状态转移，于是写完式子直接干 \(\mathrm{dp}\)。
半个小时写完，一看数据范围，答案在 \(10^{25}\) 以内。（tm要写高精）好在有int128，结束前半小时交了一发，结果直接 \(\mathrm{CE}\)，换个语言，直接听取 \(\mathrm{WA}\) 声一片。（后来发现是转移的时候数组越界了）
最终结果：在结束前五分钟在本地完成打表。并在结束前一分钟提交程序并 \(\mathrm{AC}\)。（极限拉扯）
估分：\(0+0+100=100\)
实际：\(0+0+100=100\)
还是说正解吧（
A.Exhibit
正解
本题相当于求一个最小区间，使得区间内 \(1\sim m\) 全部出现。用双指针扫一遍，不难发现如果当前区间有至少一个数与区间的第一个数相同（不含本身），那么第一个数就没有价值了，此时让左指针向右跳，每次满足条件的区间长度取最小值即可。
时间复杂度：\(O(n)\)
code
#include<bits/stdc++.h>
using namespace std;
const int N=1000005,M=2005;
int n,m;
int a[N],cnt[M],sum;
int ans=0x3f3f3f3f,ansl,ansr;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
int l=1,r;
for(r=1;r<=n;r++)
{
if(!cnt[a[r]]) sum++;
cnt[a[r]]++;
while(cnt[a[l]]>=2) cnt[a[l]]--,l++;
if(sum==m&&r-l+1<ans) ansl=l,ansr=r,ans=r-l+1;
}
printf("%d %d\n",ansl,ansr);
return 0;
}
B.国家宝藏
正解
本题就是求连通块个数，可以使用 \(\mathrm{bfs}\)。
时间复杂度：\(O(n^2)\)
（题解介绍了 \(\mathrm{Floodfill}\) 算法与并查集做法，但好像出题人疏忽了暴力）
code
#include<bits/stdc++.h>
using namespace std;
int n,ans;
const int N=1005;
int c[N][N];
int movx[]={0,-1,0,1,0};
int movy[]={0,0,-1,0,1};
queue<int> q;
void bfs(int id)
{
q.push(id);
while(!q.empty())
{
int u=q.front();
q.pop();
int x=(u-1)/n+1,y=(u-1)%n+1;
for(int i=1;i<=4;i++)
{
int xx=x+movx[i],yy=y+movy[i];
if(xx<1||xx>n||yy<1||yy>n) continue;
if(c[xx][yy]) continue;
q.push((xx-1)*n+yy);
c[xx][yy]=ans;
}
}
return;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++) scanf("%d",&c[i][j]);
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(!c[i][j])
{
c[i][j]=++ans;
bfs((i-1)*n+j);
}
}
}
printf("%d\n",ans);
return 0;
}
C.Lcm
正解
考虑最终答案的质因子，发现可以限定取得质因子的范围从而进行 \(\mathrm{dp}\)。
具体一些，设 \(f_{i,j}\) 为和为 \(i\)，质因子最小为第 \(j\) 个质数的最大的最小公倍数。
初始化：\(f_{0,i}=0\)。
转移：设 \(p_i\) 表示从小到大排的第 \(i\) 个质数，则 \(f_{i,j}=\max\{f_{i-1,j},f_{i,j+1},f_{i-p_j^k}\times p_j^k\}\)。
时间复杂度：\(O(n^3)\)（但实际上根本跑不满）
（题解限定的是使用前 \(j\) 个质数，本质上其实是一样的）
code
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=505;
__int128 f[N][N],mul=1;
int v[N],prime[N];
void primes()
{
for(int i=2;i<=n;i++)
{
if(v[i]==0)
{
prime[++m]=i;
v[i]=i;
}
for(int j=1;j<=m;j++)
{
if(v[i]<prime[j]||i*prime[j]>n) break;
v[i*prime[j]]=v[i]*prime[j];
}
}
}
inline void write(__int128 x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9) write(x/10);
putchar(x%10+'0');
}
int main()
{
cin>>n;
primes();
for(int i=0;i<=n;i++)
{
for(int j=m;j>=1;j--)
{
if(i==0) f[i][j]=1;
else
{
mul=1;
f[i][j]=f[i][j+1];
while(1)
{
mul*=prime[j];
if(mul>i) break;
f[i][j]=max(f[i-mul][j+1]*mul,f[i][j]);
}
}
if(i!=0) f[i][j]=max(f[i][j],f[i-1][j]);
}
}
write(f[n][1]);
cout<<endl;
return 0;
}
打表code
#include<bits/stdc++.h>
using namespace std;
int n;
int main()
{
scanf("%d",&n);
if(n==1) printf("1");
if(n==2) printf("2");
if(n==3) printf("3");
if(n==4) printf("4");
if(n==5) printf("6");
if(n==6) printf("6");
if(n==7) printf("12");
if(n==8) printf("15");
if(n==9) printf("20");
if(n==10) printf("30");
if(n==11) printf("30");
if(n==12) printf("60");
if(n==13) printf("60");
if(n==14) printf("84");
if(n==15) printf("105");
if(n==16) printf("140");
if(n==17) printf("210");
if(n==18) printf("210");
if(n==19) printf("420");
if(n==20) printf("420");
if(n==21) printf("420");
if(n==22) printf("420");
if(n==23) printf("840");
if(n==24) printf("840");
if(n==25) printf("1260");
if(n==26) printf("1260");
if(n==27) printf("1540");
if(n==28) printf("2310");
if(n==29) printf("2520");
if(n==30) printf("4620");
if(n==31) printf("4620");
if(n==32) printf("5460");
if(n==33) printf("5460");
if(n==34) printf("9240");
if(n==35) printf("9240");
if(n==36) printf("13860");
if(n==37) printf("13860");
if(n==38) printf("16380");
if(n==39) printf("16380");
if(n==40) printf("27720");
if(n==41) printf("30030");
if(n==42) printf("32760");
if(n==43) printf("60060");
if(n==44) printf("60060");
if(n==45) printf("60060");
if(n==46) printf("60060");
if(n==47) printf("120120");
if(n==48) printf("120120");
if(n==49) printf("180180");
if(n==50) printf("180180");
if(n==51) printf("180180");
if(n==52) printf("180180");
if(n==53) printf("360360");
if(n==54) printf("360360");
if(n==55) printf("360360");
if(n==56) printf("360360");
if(n==57) printf("471240");
if(n==58) printf("510510");
if(n==59) printf("556920");
if(n==60) printf("1021020");
if(n==61) printf("1021020");
if(n==62) printf("1141140");
if(n==63) printf("1141140");
if(n==64) printf("2042040");
if(n==65) printf("2042040");
if(n==66) printf("3063060");
if(n==67) printf("3063060");
if(n==68) printf("3423420");
if(n==69) printf("3423420");
if(n==70) printf("6126120");
if(n==71) printf("6126120");
if(n==72) printf("6846840");
if(n==73) printf("6846840");
if(n==74) printf("6846840");
if(n==75) printf("6846840");
if(n==76) printf("8953560");
if(n==77) printf("9699690");
if(n==78) printf("12252240");
if(n==79) printf("19399380");
if(n==80) printf("19399380");
if(n==81) printf("19399380");
if(n==82) printf("19399380");
if(n==83) printf("38798760");
if(n==84) printf("38798760");
if(n==85) printf("58198140");
if(n==86) printf("58198140");
if(n==87) printf("58198140");
if(n==88) printf("58198140");
if(n==89) printf("116396280");
if(n==90) printf("116396280");
if(n==91) printf("116396280");
if(n==92) printf("116396280");
if(n==93) printf("140900760");
if(n==94) printf("140900760");
if(n==95) printf("157477320");
if(n==96) printf("157477320");
if(n==97) printf("232792560");
if(n==98) printf("232792560");
if(n==99) printf("232792560");
if(n==100) printf("232792560");
if(n==101) printf("281801520");
if(n==102) printf("446185740");
if(n==103) printf("446185740");
if(n==104) printf("446185740");
if(n==105) printf("446185740");
if(n==106) printf("892371480");
if(n==107) printf("892371480");
if(n==108) printf("1338557220");
if(n==109) printf("1338557220");
if(n==110) printf("1338557220");
if(n==111) printf("1338557220");
if(n==112) printf("2677114440");
if(n==113) printf("2677114440");
if(n==114) printf("2677114440");
if(n==115) printf("2677114440");
if(n==116) printf("2677114440");
if(n==117) printf("2677114440");
if(n==118) printf("3375492120");
if(n==119) printf("3375492120");
if(n==120) printf("5354228880");
if(n==121) printf("5354228880");
if(n==122) printf("5354228880");
if(n==123) printf("5354228880");
if(n==124) printf("5354228880");
if(n==125) printf("5354228880");
if(n==126) printf("6750984240");
if(n==127) printf("6750984240");
if(n==128) printf("7216569360");
if(n==129) printf("7216569360");
if(n==130) printf("8172244080");
if(n==131) printf("12939386460");
if(n==132) printf("13385572200");
if(n==133) printf("13831757940");
if(n==134) printf("13831757940");
if(n==135) printf("25878772920");
if(n==136) printf("25878772920");
if(n==137) printf("38818159380");
if(n==138) printf("38818159380");
if(n==139) printf("41495273820");
if(n==140) printf("41495273820");
if(n==141) printf("77636318760");
if(n==142) printf("77636318760");
if(n==143) printf("82990547640");
if(n==144) printf("82990547640");
if(n==145) printf("82990547640");
if(n==146) printf("82990547640");
if(n==147) printf("82990547640");
if(n==148) printf("82990547640");
if(n==149) printf("155272637520");
if(n==150) printf("155272637520");
if(n==151) printf("165981095280");
if(n==152) printf("165981095280");
if(n==153) printf("165981095280");
if(n==154) printf("165981095280");
if(n==155) printf("165981095280");
if(n==156) printf("165981095280");
if(n==157) printf("209280511440");
if(n==158) printf("209280511440");
if(n==159) printf("232908956280");
if(n==160) printf("232908956280");
if(n==161) printf("388181593800");
if(n==162) printf("401120980260");
if(n==163) printf("414952738200");
if(n==164) printf("414952738200");
if(n==165) printf("414952738200");
if(n==166) printf("802241960520");
if(n==167) printf("802241960520");
if(n==168) printf("1203362940780");
if(n==169) printf("1203362940780");
if(n==170) printf("1203362940780");
if(n==171) printf("1203362940780");
if(n==172) printf("2406725881560");
if(n==173) printf("2406725881560");
if(n==174) printf("2406725881560");
if(n==175) printf("2406725881560");
if(n==176) printf("2406725881560");
if(n==177) printf("2406725881560");
if(n==178) printf("2872543794120");
if(n==179) printf("2872543794120");
if(n==180) printf("4813451763120");
if(n==181) printf("4813451763120");
if(n==182) printf("4813451763120");
if(n==183) printf("4813451763120");
if(n==184) printf("4813451763120");
if(n==185) printf("4813451763120");
if(n==186) printf("5745087588240");
if(n==187) printf("5745087588240");
if(n==188) printf("6141300525360");
if(n==189) printf("6141300525360");
if(n==190) printf("7220177644680");
if(n==191) printf("7220177644680");
if(n==192) printf("12033629407800");
if(n==193) printf("12033629407800");
if(n==194) printf("12033629407800");
if(n==195) printf("12033629407800");
if(n==196) printf("12033629407800");
if(n==197) printf("12033629407800");
if(n==198) printf("14440355289360");
if(n==199) printf("14841476269620");
if(n==200) printf("24067258815600");
if(n==201) printf("24067258815600");
if(n==202) printf("24067258815600");
if(n==203) printf("29682952539240");
if(n==204) printf("29682952539240");
if(n==205) printf("44524428808860");
if(n==206) printf("44524428808860");
if(n==207) printf("44524428808860");
if(n==208) printf("44524428808860");
if(n==209) printf("89048857617720");
if(n==210) printf("89048857617720");
if(n==211) printf("89048857617720");
if(n==212) printf("89048857617720");
if(n==213) printf("98675761143960");
if(n==214) printf("98675761143960");
if(n==215) printf("103489212907080");
if(n==216) printf("103489212907080");
if(n==217) printf("178097715235440");
if(n==218) printf("178097715235440");
if(n==219) printf("178097715235440");
if(n==220) printf("178097715235440");
if(n==221) printf("197351522287920");
if(n==222) printf("197351522287920");
if(n==223) printf("206978425814160");
if(n==224) printf("206978425814160");
if(n==225) printf("222622144044300");
if(n==226) printf("222622144044300");
if(n==227) printf("267146572853160");
if(n==228) printf("267146572853160");
if(n==229) printf("445244288088600");
if(n==230) printf("445244288088600");
if(n==231) printf("445244288088600");
if(n==232) printf("445244288088600");
if(n==233) printf("493378805719800");
if(n==234) printf("493378805719800");
if(n==235) printf("534293145706320");
if(n==236) printf("534293145706320");
if(n==237) printf("890488576177200");
if(n==238) printf("890488576177200");
if(n==239) printf("890488576177200");
if(n==240) printf("890488576177200");
if(n==241) printf("986757611439600");
if(n==242) printf("986757611439600");
if(n==243) printf("1034892129070800");
if(n==244) printf("1217001054108840");
if(n==245) printf("1217001054108840");
if(n==246) printf("1825501581163260");
if(n==247) printf("1825501581163260");
if(n==248) printf("1914550438780980");
if(n==249) printf("1914550438780980");
if(n==250) printf("3651003162326520");
if(n==251) printf("3651003162326520");
if(n==252) printf("3829100877561960");
if(n==253) printf("3829100877561960");
if(n==254) printf("3829100877561960");
if(n==255) printf("3829100877561960");
if(n==256) printf("4243057729190280");
if(n==257) printf("4243057729190280");
if(n==258) printf("7302006324653040");
if(n==259) printf("7302006324653040");
if(n==260) printf("7658201755123920");
if(n==261) printf("7658201755123920");
if(n==262) printf("7658201755123920");
if(n==263) printf("7658201755123920");
if(n==264) printf("8486115458380560");
if(n==265) printf("8486115458380560");
if(n==266) printf("9127507905816300");
if(n==267) printf("9127507905816300");
if(n==268) printf("10953009486979560");
if(n==269) printf("10953009486979560");
if(n==270) printf("18255015811632600");
if(n==271) printf("18255015811632600");
if(n==272) printf("19145504387809800");
if(n==273) printf("19145504387809800");
if(n==274) printf("19145504387809800");
if(n==275) printf("19145504387809800");
if(n==276) printf("21906018973959120");
if(n==277) printf("21906018973959120");
if(n==278) printf("36510031623265200");
if(n==279) printf("36510031623265200");
if(n==280) printf("38291008775619600");
if(n==281) printf("38291008775619600");
if(n==282) printf("38291008775619600");
if(n==283) printf("38291008775619600");
if(n==284) printf("42430577291902800");
if(n==285) printf("42430577291902800");
if(n==286) printf("42430577291902800");
if(n==287) printf("52331045326680120");
if(n==288) printf("54765047434897800");
if(n==289) printf("78496567990020180");
if(n==290) printf("78496567990020180");
if(n==291) printf("78496567990020180");
if(n==292) printf("78496567990020180");
if(n==293) printf("156993135980040360");
if(n==294) printf("156993135980040360");
if(n==295) printf("156993135980040360");
if(n==296) printf("156993135980040360");
if(n==297) printf("171597148629346440");
if(n==298) printf("171597148629346440");
if(n==299) printf("179967741245412120");
if(n==300) printf("179967741245412120");
if(n==301) printf("313986271960080720");
if(n==302) printf("313986271960080720");
if(n==303) printf("313986271960080720");
if(n==304) printf("313986271960080720");
if(n==305) printf("343194297258692880");
if(n==306) printf("343194297258692880");
if(n==307) printf("359935482490824240");
if(n==308) printf("359935482490824240");
if(n==309) printf("392482839950100900");
if(n==310) printf("392482839950100900");
if(n==311) printf("470979407940121080");
if(n==312) printf("470979407940121080");
if(n==313) printf("784965679900201800");
if(n==314) printf("784965679900201800");
if(n==315) printf("784965679900201800");
if(n==316) printf("784965679900201800");
if(n==317) printf("857985743146732200");
if(n==318) printf("857985743146732200");
if(n==319) printf("941958815880242160");
if(n==320) printf("941958815880242160");
if(n==321) printf("1569931359800403600");
if(n==322) printf("1569931359800403600");
if(n==323) printf("1569931359800403600");
if(n==324) printf("1569931359800403600");
if(n==325) printf("1715971486293464400");
if(n==326) printf("1715971486293464400");
if(n==327) printf("1799677412454121200");
if(n==328) printf("1799677412454121200");
if(n==329) printf("1799677412454121200");
if(n==330) printf("1799677412454121200");
if(n==331) printf("2354897039700605400");
if(n==332) printf("2354897039700605400");
if(n==333) printf("2354897039700605400");
if(n==334) printf("2459559130353965640");
if(n==335) printf("2573957229440196600");
if(n==336) printf("3689338695530948460");
if(n==337) printf("3689338695530948460");
if(n==338) printf("3689338695530948460");
if(n==339) printf("4709794079401210800");
if(n==340) printf("7378677391061896920");
if(n==341) printf("7378677391061896920");
if(n==342) printf("7378677391061896920");
if(n==343) printf("7378677391061896920");
if(n==344) printf("7378677391061896920");
if(n==345) printf("7378677391061896920");
if(n==346) printf("8320636206942139080");
if(n==347) printf("8320636206942139080");
if(n==348) printf("14757354782123793840");
if(n==349) printf("14757354782123793840");
if(n==350) printf("14757354782123793840");
if(n==351) printf("14757354782123793840");
if(n==352) printf("14757354782123793840");
if(n==353) printf("14757354782123793840");
if(n==354) printf("16641272413884278160");
if(n==355) printf("16641272413884278160");
if(n==356) printf("18446693477654742300");
if(n==357) printf("18446693477654742300");
if(n==358) printf("22136032173185690760");
if(n==359) printf("22136032173185690760");
if(n==360) printf("36893386955309484600");
if(n==361) printf("36893386955309484600");
if(n==362) printf("36893386955309484600");
if(n==363) printf("36893386955309484600");
if(n==364) printf("36893386955309484600");
if(n==365) printf("36893386955309484600");
if(n==366) printf("44272064346371381520");
if(n==367) printf("44272064346371381520");
if(n==368) printf("73786773910618969200");
if(n==369) printf("73786773910618969200");
if(n==370) printf("73786773910618969200");
if(n==371) printf("73786773910618969200");
if(n==372) printf("73786773910618969200");
if(n==373) printf("73786773910618969200");
if(n==374) printf("83206362069421390800");
if(n==375) printf("83206362069421390800");
if(n==376) printf("83206362069421390800");
if(n==377) printf("83206362069421390800");
if(n==378) printf("110680160865928453800");
if(n==379) printf("110680160865928453800");
if(n==380) printf("110680160865928453800");
if(n==381) printf("110680160865928453800");
if(n==382) printf("110680160865928453800");
if(n==383) printf("110680160865928453800");
if(n==384) printf("147573547821237938400");
if(n==385) printf("147573547821237938400");
if(n==386) printf("221360321731856907600");
if(n==387) printf("221360321731856907600");
if(n==388) printf("221360321731856907600");
if(n==389) printf("221360321731856907600");
if(n==390) printf("221360321731856907600");
if(n==391) printf("221360321731856907600");
if(n==392) printf("249619086208264172400");
if(n==393) printf("391069901726280536760");
if(n==394) printf("391069901726280536760");
if(n==395) printf("391069901726280536760");
if(n==396) printf("391069901726280536760");
if(n==397) printf("391069901726280536760");
if(n==398) printf("391069901726280536760");
if(n==399) printf("435341966072651918280");
if(n==400) printf("435341966072651918280");
if(n==401) printf("782139803452561073520");
if(n==402) printf("782139803452561073520");
if(n==403) printf("782139803452561073520");
if(n==404) printf("782139803452561073520");
if(n==405) printf("782139803452561073520");
if(n==406) printf("782139803452561073520");
if(n==407) printf("870683932145303836560");
if(n==408) printf("870683932145303836560");
if(n==409) printf("977674754315701341900");
if(n==410) printf("977674754315701341900");
if(n==411) printf("1173209705178841610280");
if(n==412) printf("1173209705178841610280");
if(n==413) printf("1955349508631402683800");
if(n==414) printf("1955349508631402683800");
if(n==415) printf("1955349508631402683800");
if(n==416) printf("1955349508631402683800");
if(n==417) printf("1955349508631402683800");
if(n==418) printf("1955349508631402683800");
if(n==419) printf("2346419410357683220560");
if(n==420) printf("2346419410357683220560");
if(n==421) printf("3910699017262805367600");
if(n==422) printf("3910699017262805367600");
if(n==423) printf("3910699017262805367600");
if(n==424) printf("3910699017262805367600");
if(n==425) printf("3910699017262805367600");
if(n==426) printf("3910699017262805367600");
if(n==427) printf("4353419660726519182800");
if(n==428) printf("4353419660726519182800");
if(n==429) printf("4500993208547757121200");
if(n==430) printf("4500993208547757121200");
if(n==431) printf("5866048525894208051400");
if(n==432) printf("5866048525894208051400");
if(n==433) printf("5866048525894208051400");
if(n==434) printf("5866048525894208051400");
if(n==435) printf("5866048525894208051400");
if(n==436) printf("5866048525894208051400");
if(n==437) printf("7821398034525610735200");
if(n==438) printf("7821398034525610735200");
if(n==439) printf("11732097051788416102800");
if(n==440) printf("11732097051788416102800");
if(n==441) printf("11732097051788416102800");
if(n==442) printf("11732097051788416102800");
if(n==443) printf("11732097051788416102800");
if(n==444) printf("11732097051788416102800");
if(n==445) printf("13060258982179557548400");
if(n==446) printf("13060258982179557548400");
if(n==447) printf("13502979625643271363600");
if(n==448) printf("13502979625643271363600");
if(n==449) printf("13502979625643271363600");
if(n==450) printf("13502979625643271363600");
if(n==451) printf("14727526086287586171600");
if(n==452) printf("23073124201850551668840");
if(n==453) printf("23073124201850551668840");
if(n==454) printf("23855264005303112742360");
if(n==455) printf("23855264005303112742360");
if(n==456) printf("23855264005303112742360");
if(n==457) printf("23855264005303112742360");
if(n==458) printf("23855264005303112742360");
if(n==459) printf("23855264005303112742360");
if(n==460) printf("46146248403701103337680");
if(n==461) printf("46146248403701103337680");
if(n==462) printf("47710528010606225484720");
if(n==463) printf("47710528010606225484720");
if(n==464) printf("47710528010606225484720");
if(n==465) printf("47710528010606225484720");
if(n==466) printf("47710528010606225484720");
if(n==467) printf("47710528010606225484720");
if(n==468) printf("57682810504626379172100");
if(n==469) printf("57682810504626379172100");
if(n==470) printf("69219372605551655006520");
if(n==471) printf("69219372605551655006520");
if(n==472) printf("115365621009252758344200");
if(n==473) printf("115365621009252758344200");
if(n==474) printf("119276320026515563711800");
if(n==475) printf("119276320026515563711800");
if(n==476) printf("119276320026515563711800");
if(n==477) printf("119276320026515563711800");
if(n==478) printf("138438745211103310013040");
if(n==479) printf("138438745211103310013040");
if(n==480) printf("230731242018505516688400");
if(n==481) printf("230731242018505516688400");
if(n==482) printf("238552640053031127423600");
if(n==483) printf("238552640053031127423600");
if(n==484) printf("238552640053031127423600");
if(n==485) printf("238552640053031127423600");
if(n==486) printf("238552640053031127423600");
if(n==487) printf("238552640053031127423600");
if(n==488) printf("265558599304317670150800");
if(n==489) printf("265558599304317670150800");
if(n==490) printf("346096863027758275032600");
if(n==491) printf("346096863027758275032600");
if(n==492) printf("357828960079546691135400");
if(n==493) printf("357828960079546691135400");
if(n==494) printf("357828960079546691135400");
if(n==495) printf("357828960079546691135400");
if(n==496) printf("461462484037011033376800");
if(n==497) printf("461462484037011033376800");
if(n==498) printf("692193726055516550065200");
if(n==499) printf("692193726055516550065200");
if(n==500) printf("715657920159093382270800");
return 0;
}