首先对称的时候一定是公平的,因为没有子也是对称的.

所以爆搜一下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include<bits/stdc++.h>
using namespace std;
#define enter fout<<"\n";
#define space fout<<" ";
#define dot fout<<",";
#define oui fout<<"Yes\n";
#define non fout<<"No\n";
#define si fout<<"?";
#define i32 int
#define u32 unsigned int
#define i64 long long
#define u64 unsigned long long
#define i128 __int128
#define u128 unsigned __int128
#define debug(x) fout<<#x<<"="<<x<<"\n";
#define vdebug(a,n) fout<<#a<<"=[";for(int i=0;i<=n;++i)fout<<a[i]<<" ";fout<<"]\n";
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
namespace fastio{
    const int bufl=1<<20;
    const double base1[16]={1,1e-1,1e-2,1e-3,1e-4,1e-5,1e-6,1e-7,1e-8,1e-9,1e-10,1e-11,1e-12,1e-13,1e-14,1e-15};
    const double base2[16]={1,1e1,1e2,1e3,1e4,1e5,1e6,1e7,1e8,1e9,1e10,1e11,1e12,1e13,1e14,1e15};
    struct IN{
        FILE *IT;char ibuf[bufl],*is=ibuf,*it=ibuf;
        IN(){IT=stdin;}IN(char *a){IT=fopen(a,"r");}
        inline char getChar(){if(is==it){it=(is=ibuf)+fread(ibuf,1,bufl,IT);if(is==it)return EOF;}return *is++;}
        template<typename Temp>inline void getInt(Temp &a){a=0;int b=0,c=getChar();while(c<48||c>57)b^=(c==45),c=getChar();while(c>=48&&c<=57)a=(a<<1)+(a<<3)+c-48,c=getChar();if(b)a=-a;}
        template<typename Temp>inline void getDouble(Temp &a){a=0;int b=0,c=getChar(),d=0;__int128 e=0,f=0;while(c<48||c>57)b^=(c==45),c=getChar();while(c>=48&&c<=57)e=(e<<1)+(e<<3)+c-48,c=getChar();if(c==46){c=getChar();while(c>=48&&c<=57)d++,f=(f<<1)+(f<<3)+c-48,c=getChar();}a=e+base1[d]*f;if(b)a=-a;}
        IN& operator>>(char &a){a=getChar();while(a<=32)a=getChar();return *this;}
        IN& operator>>(char *a){do{*a=getChar();}while(*a<=32);while(*a>32)*++a=getChar();*a=0;return *this;}
        IN& operator>>(string &a){a.clear();char b=getChar();while(b<=32)b=getChar();while(b>32)a+=b,b=getChar();return *this;}
        IN& operator>>(int &a){getInt(a);return *this;}
        IN& operator>>(long long &a){getInt(a);return *this;}
        IN& operator>>(__int128 &a){getInt(a);return *this;}
        IN& operator>>(float &a){getDouble(a);return *this;}
        IN& operator>>(double &a){getDouble(a);return *this;}
        IN& operator>>(long double &a){getDouble(a);return *this;}
    };
    struct OUT{
        FILE *IT;char obuf[bufl],*os=obuf,*ot=obuf+bufl;int Eps;long double Acc;
        OUT(){IT=stdout,Eps=6,Acc=0.5;}OUT(char *a){IT=fopen(a,"w"),Eps=6,Acc=0.5;}
        inline void ChangEps(int x=6){Eps=x;}
        inline void flush(){fwrite(obuf,1,os-obuf,IT);os=obuf;}
        inline void putChar(int a){*os++=a;if(os==ot)flush();}
        template<typename Temp>inline void putInt(Temp a){if(a<0){putChar(45);a=-a;}if(a<10){putChar(a+48);return;}putInt(a/10);putChar(a%10+48);}
        template<typename Temp>inline void putLeading(Temp a,int b){if(!b)return;putLeading(a/10,b-1);putChar(a%10+48);}
        template<typename Temp>inline void putDouble(Temp a){if(a<0){putChar(45);a=-a;}__int128 ff=(a-(__int128)a)*base2[Eps+2],gg=0;ff+=50;while(ff>0){ff/=10;gg++;}__int128 b=a;if(gg==Eps+3){putInt(b+1);}else{putInt(b);}a-=b;a*=base2[Eps];b=a+Acc;putChar(46);putLeading(b,Eps);}
        OUT& operator<<(char a){putChar(a);return *this;}
        OUT& operator<<(const char *a){while(*a)putChar(*a++);return *this;}
        OUT& operator<<(string a){for(auto c:a)putChar(c);return *this;}
        OUT& operator<<(int a){putInt(a);return *this;}
        OUT& operator<<(long long a){putInt(a);return *this;}
        OUT& operator<<(__int128 a){putInt(a);return *this;}
        OUT& operator<<(unsigned int a){putInt(a);return *this;}
        OUT& operator<<(unsigned long long a){putInt(a);return *this;}
        OUT& operator<<(unsigned __int128 a){putInt(a);return *this;}
        OUT& operator<<(float a){putDouble(a);return *this;}
        OUT& operator<<(double a){putDouble(a);return *this;}
        OUT& operator<<(long double a){putDouble(a);return *this;}
        ~OUT(){flush();}
    };
}
fastio::IN fin;
fastio::OUT fout;



long long n,m,res;

unordered_map<int,unordered_map<int,unordered_map<int,unordered_map<int,int>>>>mp;

void dfs(int dep,int c1,int c2,int c3,int c4){
    if(dep>n){
        if((c1==c2&&c3==c4)|((c1-c2!=0)&&((c1-c2)*4==(c4-c3)))){
            res++;
        }
        mp[c1][c2][c3][c4]++;
        return;
    }
    dfs(dep+1,c1+1,c2,c3,c4);
    dfs(dep+1,c1,c2+1,c3,c4);
    dfs(dep+1,c1,c2,c3+1,c4);
    dfs(dep+1,c1,c2,c3,c4+1);
}





//#define NaraFluorine
int main(){
    fin>>n;
    dfs(1,0,0,0,0);
    fout<<res;
    // enter;
    // for(auto i:mp){
    //     for(auto j:i.second){
    //         for(auto k:j.second){
    //             for(auto l:k.second){
    //                 if(l.second<=90)
    //                 fout<<i.first<<" "<<j.first<<" "<<k.first<<" "<<l.first<<" "<<l.second<<"\n";
    //             }
    //         }
    //     }
    // }
    return 0;
}

同时测试样例发现

1
2
sage: factor(63594)
2 * 3^2 * 3533

发现 $63594$ 这个数字有一个大质数因数,所以答案更有可能是加出来的,而不是乘出来的,也就是说可能有多种情况.

直接爆搜完全对称的能得到 63504 ,后续发现 2 0 0 8 和 0 2 8 0 这种也是可以的,加进去得到了小样例的答案.

至此我们有了一个大致思路:分别枚举多少个子是什么情况,然后都乘起来即可,复杂度O(n^3).
但这显然会超时,考虑优化:

如果前面两种棋子确定了,后面的总和也确定了,那么这个局面是唯一的.

所以直接枚举前面两个,后面的能算出来.

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include<bits/stdc++.h>
using namespace std;
#define enter fout<<"\n";
#define space fout<<" ";
#define dot fout<<",";
#define oui fout<<"Yes\n";
#define non fout<<"No\n";
#define si fout<<"?";
#define i32 int
#define u32 unsigned int
#define i64 long long
#define u64 unsigned long long
#define i128 __int128
#define u128 unsigned __int128
#define debug(x) fout<<#x<<"="<<x<<"\n";
#define vdebug(a,n) fout<<#a<<"=[";for(int i=0;i<=n;++i)fout<<a[i]<<" ";fout<<"]\n";
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
namespace fastio{
    const int bufl=1<<20;
    const double base1[16]={1,1e-1,1e-2,1e-3,1e-4,1e-5,1e-6,1e-7,1e-8,1e-9,1e-10,1e-11,1e-12,1e-13,1e-14,1e-15};
    const double base2[16]={1,1e1,1e2,1e3,1e4,1e5,1e6,1e7,1e8,1e9,1e10,1e11,1e12,1e13,1e14,1e15};
    struct IN{
        FILE *IT;char ibuf[bufl],*is=ibuf,*it=ibuf;
        IN(){IT=stdin;}IN(char *a){IT=fopen(a,"r");}
        inline char getChar(){if(is==it){it=(is=ibuf)+fread(ibuf,1,bufl,IT);if(is==it)return EOF;}return *is++;}
        template<typename Temp>inline void getInt(Temp &a){a=0;int b=0,c=getChar();while(c<48||c>57)b^=(c==45),c=getChar();while(c>=48&&c<=57)a=(a<<1)+(a<<3)+c-48,c=getChar();if(b)a=-a;}
        template<typename Temp>inline void getDouble(Temp &a){a=0;int b=0,c=getChar(),d=0;__int128 e=0,f=0;while(c<48||c>57)b^=(c==45),c=getChar();while(c>=48&&c<=57)e=(e<<1)+(e<<3)+c-48,c=getChar();if(c==46){c=getChar();while(c>=48&&c<=57)d++,f=(f<<1)+(f<<3)+c-48,c=getChar();}a=e+base1[d]*f;if(b)a=-a;}
        IN& operator>>(char &a){a=getChar();while(a<=32)a=getChar();return *this;}
        IN& operator>>(char *a){do{*a=getChar();}while(*a<=32);while(*a>32)*++a=getChar();*a=0;return *this;}
        IN& operator>>(string &a){a.clear();char b=getChar();while(b<=32)b=getChar();while(b>32)a+=b,b=getChar();return *this;}
        IN& operator>>(int &a){getInt(a);return *this;}
        IN& operator>>(long long &a){getInt(a);return *this;}
        IN& operator>>(__int128 &a){getInt(a);return *this;}
        IN& operator>>(float &a){getDouble(a);return *this;}
        IN& operator>>(double &a){getDouble(a);return *this;}
        IN& operator>>(long double &a){getDouble(a);return *this;}
    };
    struct OUT{
        FILE *IT;char obuf[bufl],*os=obuf,*ot=obuf+bufl;int Eps;long double Acc;
        OUT(){IT=stdout,Eps=6,Acc=0.5;}OUT(char *a){IT=fopen(a,"w"),Eps=6,Acc=0.5;}
        inline void ChangEps(int x=6){Eps=x;}
        inline void flush(){fwrite(obuf,1,os-obuf,IT);os=obuf;}
        inline void putChar(int a){*os++=a;if(os==ot)flush();}
        template<typename Temp>inline void putInt(Temp a){if(a<0){putChar(45);a=-a;}if(a<10){putChar(a+48);return;}putInt(a/10);putChar(a%10+48);}
        template<typename Temp>inline void putLeading(Temp a,int b){if(!b)return;putLeading(a/10,b-1);putChar(a%10+48);}
        template<typename Temp>inline void putDouble(Temp a){if(a<0){putChar(45);a=-a;}__int128 ff=(a-(__int128)a)*base2[Eps+2],gg=0;ff+=50;while(ff>0){ff/=10;gg++;}__int128 b=a;if(gg==Eps+3){putInt(b+1);}else{putInt(b);}a-=b;a*=base2[Eps];b=a+Acc;putChar(46);putLeading(b,Eps);}
        OUT& operator<<(char a){putChar(a);return *this;}
        OUT& operator<<(const char *a){while(*a)putChar(*a++);return *this;}
        OUT& operator<<(string a){for(auto c:a)putChar(c);return *this;}
        OUT& operator<<(int a){putInt(a);return *this;}
        OUT& operator<<(long long a){putInt(a);return *this;}
        OUT& operator<<(__int128 a){putInt(a);return *this;}
        OUT& operator<<(unsigned int a){putInt(a);return *this;}
        OUT& operator<<(unsigned long long a){putInt(a);return *this;}
        OUT& operator<<(unsigned __int128 a){putInt(a);return *this;}
        OUT& operator<<(float a){putDouble(a);return *this;}
        OUT& operator<<(double a){putDouble(a);return *this;}
        OUT& operator<<(long double a){putDouble(a);return *this;}
        ~OUT(){flush();}
    };
}
fastio::IN fin;
fastio::OUT fout;



long long fac[200010],defac[200010];
const int mod=989898989;
template<typename T1,typename T2,typename T3>
T1 qp(T1 b,T2 po,T3 p){
    T1 res=1;
    while(po>0){
        if(po&1)
            res=res*b%p;
        b=b*b%p;
        po>>=1;
    }
    return res;
}
void init(int n){
    fac[0]=defac[0]=1;
    for(int i=1;i<=n;++i){
        fac[i]=(i*fac[i-1])%mod;
    }
    defac[n]=qp(fac[n],mod-2,mod);
    for(int i=n-1;i>0;--i){
        defac[i]=defac[i+1]*(i+1)%mod;
    }
}
long long C(int n,int m){
    if(m==0)return 1;
    if(m<0||m>n)return 0;
    return fac[n]*defac[m]%mod*defac[n-m]%mod;
}
long long A(int n,int m){
    if(m==0)return 1;
    if(m<0||m>n)return 0;
    return fac[n]*defac[n-m]%mod;
}







long long n,m,res=0;
//#define NaraFluorine
int main(){
    init(100000);
    int lim=9898;
    fin>>lim;
    for(int i=0;i<=lim;++i){
        for(int j=0;j+i<=lim;++j){
            int ress=lim-i-j;
            if(ress<4*abs(i-j))continue;
            int k=4*abs(i-j)+(ress-4*abs(i-j))/2,l=(ress-4*abs(i-j))/2;
            if(i+j+k+l!=lim)continue;
            // fout<<i<<" "<<j<<" "<<k<<" "<<l<<" "<<C(lim,i)*C(lim-i,j)%mod*C(lim-i-j,k)%mod*C(lim-i-j-k,l)%mod<<"\n";
            res+=C(lim,i)*C(lim-i,j)%mod*C(lim-i-j,k)%mod*C(lim-i-j-k,l)%mod;
            res%=mod;
        }
    }
    fout<<res;
    return 0;
}