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
| #define int long long
const int mod=65521;
inline int power(int x,int y=mod-2) {
if (y<=0) return 1;
int sum=1;
while (y) {
if (y&1) sum=sum*x%mod;
x=x*x%mod;y>>=1;
}
return sum;
}
int k,n,base;
struct Mat {
int a[55][55];
Mat (void) {memset(a,0,sizeof(a));}
inline void clear(void) {
memset(a,0,sizeof(a));
for (int i=0;i<=base;i++) a[i][i]=1;
}
void print(void) {
int i,j;
for (i=0;i<=base;i++,put()) for (j=0;j<=base;j++) printf("%lld ",a[i][j]);
put();
}
Mat operator *(const Mat &x) const {
Mat ans;
int i,j,k;
for (k=0;k<=base;k++) {
for (i=0;i<=base;i++) {
int r=a[i][k];
for (j=0;j<=base;j++)
ans.a[i][j]=(ans.a[i][j]+r*x.a[k][j])%mod;
}
}
return ans;
}
}tmp,Ans;
int ans,g[65],p[105],v[105],tot,s[105],id[555555];
inline void calc(void) {
int i,cnt=0,sum=0;
for (i=1;i<=k;i++) v[i]=0;
for (i=1;i<=k;i++) if (!v[p[i]]) v[p[i]]=++cnt,assert(cnt<=k&&p[i]<=k);
for (i=1;i<=k;i++) sum=sum*10+v[p[i]];
if (!id[sum]) ++tot,id[sum]=tot,s[tot]=sum;
}
inline void dfs(int now) {
if (now>k) return calc(),void();
for (int i=1;i<=k;i++) p[now]=i,dfs(now+1);
}
int fa[105],h[105];
inline int getfa(int x) {return x==fa[x]?x:fa[x]=getfa(fa[x]);}
inline void solve(int e) {
int i,j,nums=0;
for (i=1;i<=k;i++) fa[i]=i;
for (i=1;i<=k;i++) {
for (j=i+1;j<=k;j++) {
++nums;
if ((e>>nums-1)&1) {
if (getfa(i)==getfa(j)) return ;
fa[getfa(i)]=getfa(j);
}
}
}
int sum=0,cnt=0;
for (i=1;i<=k;i++) p[i]=getfa(i);
for (i=1;i<=k;i++) v[i]=0;
for (i=1;i<=k;i++) if (!v[p[i]]) v[p[i]]=++cnt;
for (i=1;i<=k;i++) sum=sum*10+v[p[i]];
h[id[sum]]++;
}
inline void add(int S,int e) {
int i,j;
int now=s[S];
for (i=k;i>=1;i--) p[i]=now%10,now/=10;
for (i=1;i<=k+1;i++) fa[i]=i;
for (i=1;i<=k;i++)
for (j=i+1;j<=k;j++)
if (p[i]==p[j])
fa[i]=getfa(j);
for (i=1;i<=k;i++) if ((e>>i-1)&1) {
if (getfa(i)==getfa(k+1)) return ;
fa[getfa(i)]=getfa(k+1);
}
if (getfa(1)==1) return ;
int sum=0,cnt=0;
for (i=2;i<=k+1;i++) p[i]=getfa(i);
for (i=1;i<=k+1;i++) v[i]=0;
for (i=2;i<=k+1;i++) if (!v[p[i]]) v[p[i]]=++cnt;
for (i=2;i<=k+1;i++) sum=sum*10+v[p[i]];
++tmp.a[S][id[sum]];
}
signed main(void){
int i,j,t;
read(k);read(n);
base=1<<k;dfs(1);
for (i=0;i<(1<<(k*(k-1)/2));i++) solve(i);
for (i=1;i<=tot;i++) {
for (j=0;j<base;j++)
add(i,j);
}
base=tot+1;
n-=k;Ans.clear();
while (n) {
if (n&1) Ans=Ans*tmp;
tmp=tmp*tmp;n>>=1;
}
for (i=1;i<=base;i++) ans=(ans+h[i]*Ans.a[i][1])%mod;
printf("%lld",ans);
return 0;
}
|