P5879【放棋子】打表方法

· · 个人记录

生成

参看题解题解 P5879 【放棋子】。

#include<bits/stdc++.h>
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(register int i=(a);i>=(b);--i)
using namespace std;
const int maxn=110;
inline void write(__int128 x) {
    if(x<0) { putchar('-');x=-x;}
    if(x>9) write(x/10);
    putchar(x%10+48);
}
int n;
__int128 M=1,f[maxn][maxn][2],ans[2];
int main()
{
    freopen("dabiao.out","w",stdout);
    For(i,1,30) M*=10;
    for(n=1;n<=100;n++)
    {
        memset(f,0,sizeof(f));
        ans[0]=ans[1]=0;
        For(i,1,n) f[i][0][0]=1;
        For(i,1,n)
            For(j,1,i)
            {
                f[i][j][0]=(f[i][j-1][0]+f[i-1][j][0])%M;
                f[i][j][1]=f[i][j-1][1]+f[i-1][j][1]+(f[i][j-1][0]+f[i-1][j][0])/M;
            }
        For(i,1,n) ans[0]=(ans[0]+f[n][i][0]);
        ans[1]=ans[0]/M;
        ans[0]%=M;
        For(i,1,n) ans[1]+=f[n][i][1];
        putchar('"');
        if(ans[1]!=0)
        {
            write(ans[1]);
            if(ans[0]<=M/10) cout<<0;
        }
        write(ans[0]);
        putchar('"');
        putchar(',');
        cout<<endl;
    }
    return 0;
}

打表代码（112行）

#include<bits/stdc++.h>
using namespace std;
string s[110]={
" ",
"1",
"4",
"13",
"41",
"131",
"428",
"1429",
"4861",
"16795",
"58785",
"208011",
"742899",
"2674439",
"9694844",
"35357669",
"129644789",
"477638699",
"1767263189",
"6564120419",
"24466267019",
"91482563639",
"343059613649",
"1289904147323",
"4861946401451",
"18367353072151",
"69533550916003",
"263747951750359",
"1002242216651367",
"3814986502092303",
"14544636039226908",
"55534064877048197",
"212336130412243109",
"812944042149730763",
"3116285494907301261",
"11959798385860453491",
"45950804324621742363",
"176733862787006701399",
"680425371729975800389",
"2622127042276492108819",
"10113918591637898134019",
"39044429911904443959239",
"150853479205085351660699",
"583300119592996693088039",
"2257117854077248073253719",
"8740328711533173390046319",
"33868773757191046886429489",
"131327898242169365477991899",
"509552245179617138054608571",
"1978261657756160653623774455",
"7684785670514316385230816155",
"29869166945772625950142417511",
"116157871455782434250553845879",
"451959718027953471447609509423",
"1759414616608818870992479875971",
"6852456927844873497549658464311",
"26700952856774851904245220912663",
"104088460289122304033498318812079",
"405944995127576985730643443367111",
"1583850964596120042686772779038895",
"6182127958584855650487080847216335",
"24139737743045626825711458546273311",
"94295850558771979787935384946380124",
"368479169875816659479009042713546949",
"1440418573150919668872489894243865349",
"5632681584560312734993915705849145099",
"22033725021956517463358552614056949949",
"86218923998960285726185640663701108499",
"337485502510215975556783793455058624699",
"1321422108420282270489942177190229544599",
"5175569924646105559418940193995065716349",
"20276890389709399862928998568254641025699",
"79463489365077377841208237632349268884499",
"311496878311103321137536291518809134027239",
"1221395654430378811828760722007962130791019",
"4790408930363303911328386208394864461024519",
"18793142726809884575211361279087545193250039",
"73745243611532458459690151854647329239335599",
"289450081175264899454283846029490767264392229",
"1136359577947336271931632877004667456667613939",
"4462290049988320482463241297506133183499654739",
"17526585015616776834735140517915655636396234279",
"68854441132780194707888052034668647142985206099",
"270557451039395118028642463289168566420671280439",
"1063353702922273835973036658043476458723103404519",
"4180080073556524734514695828170907458428751314319",
"16435314834665426797069144960762886143367590394939",
"64633260585762914370496637486146181462681535260999",
"254224158304000796523953440778841647086547372026599",
"1000134600800354781929399250536541864362461089950799",
"3935312233584004685417853572763349509774031680023799",
"15487357822491889407128326963778343232013931127835599",
"60960876535340415751462563580829648891969728907437999",
"239993345518077005168915776623476723006280827488229599",
"944973797977428207852605870454939596837230758234904049",
"3721443204405954385563870541379246659709506697378694299",
"14657929356129575437016877846657032761712954950899755099",
"57743358069601357782187700608042856334020731624756610999",
"227508830794229349661819540395688853956041682601541047339",
"896519947090131496687170070074100632420837521538745909319",
"3533343320884635898708258511468514257188006702535057407319"
};
int main()
{
    int n;
    cin>>n;
    cout<<s[n]<<endl;
    return 0;
}

AC记录