第二十七场 Exhibit 国家宝藏 Lcm

第二十七场 Exhibit 国家宝藏 Lcm

考试时发现那场已经考过了,于是开始倒着考。

考场上顺序开题。

\(\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

第二十七场 Exhibit 国家宝藏 Lcm

正解

本题相当于求一个最小区间,使得区间内 \(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.国家宝藏

第二十七场 Exhibit 国家宝藏 Lcm

正解

本题就是求连通块个数,可以使用 \(\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

第二十七场 Exhibit 国家宝藏 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;
}
上一篇:acwing 1027 方格取数 算法提高课


下一篇:【数据结构与算法】蓄水池抽样算法(Reservoir Sampling)