解题报告
JZOJ 4786 小a的强迫症题目分析代码
JZOJ 4787 数格子题目分析代码
JZOJ 4788 序列题目分析代码
JZOJ 4786 小a的强迫症
题目
有
n
n
n种颜色的珠子，第
i
i
i种颜色的珠子有
a
i
a_i
ai个，问有多少种排列，满足第
i
i
i种颜色的最后一个珠子，必然在第
i
+
1
i+1
i+1种颜色的最后一个珠子的前面
分析
考虑倒序，对于每种排列，把最后一颗珠子放在最后一位，剩下的依照组合随意放置，那么一层层剥开，设
s
i
=
∑
j
=
1
i
a
i
s_i=\sum_{j=1}^i a_i
si=∑j=1iai答案即为
∑
i
=
2
n
C
s
i
−
1
a
i
−
1
\sum_{i=2}^{n}C_{s_i-1}^{a_i-1}
i=2∑nCsi−1ai−1
代码
#include <cstdio>
#include <cctype>
#define rr register
using namespace std
;
const int mod
=998244353;
int n
,a
[100001],sum
,inv
[500001],fac
[500001],ans
=1;
inline signed iut(){
rr
int ans
=0; rr
char c
=getchar();
while (!isdigit(c
)) c
=getchar();
while (isdigit(c
)) ans
=(ans
<<3)+(ans
<<1)+(c
^48),c
=getchar();
return ans
;
}
signed main(){
n
=iut(); inv
[0]=fac
[0]=inv
[1]=fac
[1]=1;
for (rr
int i
=1;i
<=n
;++i
) a
[i
]=iut(),sum
+=a
[i
];
for (rr
int i
=2;i
<=sum
;++i
) inv
[i
]=1ll*(mod
-mod
/i
)*inv
[mod
%i
]%mod
;
for (rr
int i
=2;i
<=sum
;++i
) fac
[i
]=1ll*fac
[i
-1]*i
%mod
,inv
[i
]=1ll*inv
[i
-1]*inv
[i
]%mod
;
for (rr
int i
=n
;i
>1;--i
)
ans
=1ll*ans
*fac
[sum
-1]%mod
*inv
[a
[i
]-1]%mod
*inv
[sum
-a
[i
]]%mod
,sum
-=a
[i
];
return !printf("%d",ans
);
}
JZOJ 4787 数格子
题目
用
2
×
1
2\times 1
2×1的骨牌完全覆盖
4
×
n
4\times n
4×n的棋盘，问共有多少种方案
分析
类比于POJ 2411 Mondriaan’s Dream,可以建立一个状压的矩阵，然而通项公式，可以得到
F
n
=
F
n
−
1
+
5
×
F
n
−
2
+
F
n
−
3
−
F
n
−
4
F_n=F_{n-1}+5\times F_{n-2}+F_{n-3}-F_{n-4}
Fn=Fn−1+5×Fn−2+Fn−3−Fn−4,然而我证明不出来，但是一波矩阵乘法就可以了
代码
#include <cstdio>
#include <cstring>
#define rr register
using namespace std
;
struct maix
{int p
[4][4];}A
,ANS
;
int n
,mod
;
inline maix
mul(maix A
,maix B
){
rr maix C
;
for (rr
int i
=0;i
<4;++i
)
for (rr
int j
=0;j
<4;++j
) C
.p
[i
][j
]=0;
for (rr
int i
=0;i
<4;++i
)
for (rr
int j
=0;j
<4;++j
)
for (rr
int k
=0;k
<4;++k
)
C
.p
[i
][j
]=(1ll*A
.p
[i
][k
]*B
.p
[k
][j
]+C
.p
[i
][j
])%mod
;
return C
;
}
signed main(){
while (1){
memset(ANS
.p
,0,sizeof(ANS
.p
));
memset(A
.p
,0,sizeof(A
.p
));
scanf("%d%d",&n
,&mod
);
if (!n
&&!mod
) return 0;
if (n
==1) {printf("1\n"); continue;}
if (n
==2) {printf("5\n"); continue;}
if (n
==3) {printf("11\n"); continue;}
ANS
.p
[0][0]=ANS
.p
[1][1]=1,ANS
.p
[2][2]=1,ANS
.p
[3][3]=1;
A
.p
[0][3]=-1,A
.p
[1][0]=1,A
.p
[2][1]=1,A
.p
[3][2]=1,A
.p
[2][3]=5,A
.p
[1][3]=1,A
.p
[3][3]=1;
for (n
-=3;n
;n
>>=1,A
=mul(A
,A
))
if (n
&1) ANS
=mul(ANS
,A
);
rr
int ans
[4]={0,0,0,0},h
[4]={1,1,5,11};
for (rr
int j
=0;j
<4;++j
)
for (rr
int k
=0;k
<4;++k
)
ans
[j
]=(1ll*h
[k
]*ANS
.p
[k
][j
]+ans
[j
])%mod
;
printf("%d\n",ans
[3]);
}
}
JZOJ 4788 序列
题目
n
n
n个
0
∼
3
0\sim 3
0∼3数，可以选取一段区间加1，当变成4时自动变成0，问最少操作多少次使这
n
n
n个数变成另外
n
n
n个
0
∼
3
0\sim 3
0∼3的数
分析
类比于洛谷 1969 积木大赛，如果没有变成0的限制，答案即为
∑
max
{
0
,
a
i
−
a
i
−
1
}
\sum \max\{0,a_i-a_{i-1}\}
∑max{0,ai−ai−1} 为什么呢，根据贪心，假设
a
i
≥
a
i
−
1
a_i\geq a_{i-1}
ai≥ai−1,那么就要再增加
a
i
−
a
i
−
1
a_i-a_{i-1}
ai−ai−1，倘若小于，那么答案显然是不需要增加的 然而，这道题是加强版，那怎么做呢，区间
[
i
∼
j
]
[i\sim j]
[i∼j]需要取模当且仅当
a
j
−
a
j
−
1
+
4
≤
a
i
+
1
−
a
i
a_j-a_{j-1}+4\leq a_{i+1}-a_{i}
aj−aj−1+4≤ai+1−ai，所以说需要统计个数，再求解
代码
#include <cstdio>
#include <cctype>
#define rr register
using namespace std
;
int a
[100001];
inline signed iut(){
rr
int ans
=0; rr
char c
=getchar();
while (!isdigit(c
)) c
=getchar();
while (isdigit(c
)) ans
=(ans
<<3)+(ans
<<1)+(c
^48),c
=getchar();
return ans
;
}
signed main(){
for (rr
int t
=iut();t
;--t
){
rr
int n
=iut(),ans
=0,lazy
[5]={0,0,0,0,0};
for (rr
int i
=1;i
<=n
;++i
) a
[i
]=iut();
for (rr
int i
=1;i
<=n
;++i
) a
[i
]=(iut()-a
[i
]+4)&3;
for (rr
int i
=1;i
<=n
;++i
) ans
+=a
[i
]>a
[i
-1]?a
[i
]-a
[i
-1]:0;
for (rr
int i
=2;i
<=n
;++i
){
rr
int now
=a
[i
]-a
[i
-1];
if (now
>0){
if (lazy
[1]&&now
>1) --lazy
[1],++lazy
[now
],ans
-=now
-1;
else if (lazy
[2]&&now
>2) --lazy
[2],++lazy
[now
],ans
-=now
-2;
}else ++lazy
[now
+4];
}
printf("%d\n",ans
);
}
return 0;
}
