【题解】牛客NOIP暑期七天营-提高组6
总结
按照NOIp惯例，本场比赛T1是签到题。从大家签到情况来看，符合预期，基本上写二维差分的人都拿到了满分。
有几位选手T1拿了75,原因是使用了快速读入导致MLE,这是我没有预期的。
T2属于一个计数题，是使用DP进行计数的套路题。m=1实际上是m=0的扩展。
T3是一道典型的组合数恒等变换的题目，属于思维题/数学能力题。(众所周知OI是小学奥数)
T1一血：13min38s 由选手Dashes 拿下。
T2一血：18min19s 由选手guyan364拿下。
T3一血：1h0min19s 由选手cccgift拿下。
开场大约2h的时候，第一位选手 Owen_codeisking AK.
本次比赛每道题都下发了较强的大样例，特别是T3对于每一组数据都下发了相同规模的样例。其他出题人做得到吗
做到Pretests passed的人应该都能A掉此题。
T1 积木大赛
部分分设置
30%纯暴力
50%每一维单独差分
另外20% 一维差分提示正解。
解题思路
首先这并不是在线的询问，而是只询问一次，所以我们考虑对每个操作差分一下。
差分完毕以后，我们用差分数组还原整个原始数组，我们就得到了每个位置上有多少个方块。
我们对每一个格子，如果他四周有比他矮的格子，就把答案加上他们的差值。同样的对于每个格子，如果有方块，就把答案加。
由于最多释放个方块，答案不可能超过
（实际上上限并不是这个数字，但这个数字要比答案上限大），并不会爆long long型，考虑用long long.
考察知识点
二维差分
代码实现
//Author:Venn
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn = 5010;
int a[maxn][maxn];
int n,m,q;
ll ans = 0;
int main() {
scanf("%d%d%d",&n,&m,&q);
while(q--) {
int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
++a[x1][y1];
--a[x2+1][y1];
--a[x1][y2+1];
++a[x2+1][y2+1];
}
for(int i=1;i<=n+1;++i)
for(int j=1;j<=m+1;++j)
a[i][j]+=a[i-1][j];
for(int i=1;i<=n+1;++i)
for(int j=1;j<=m+1;++j)
a[i][j]+=a[i][j-1];
for(int i=1;i<=n+1;++i)
for(int j=1;j<=m+1;++j) {
ans += abs(a[i][j-1]-a[i][j]) + abs(a[i-1][j]-a[i][j]) ;
if(a[i][j]) ans+=2;
}
printf("%lld\n",ans);
return 0;
}
T2 破碎的序列
部分分设置
：
，
的个数不超过
，可以考虑枚举每个等于
的
，然后
检验是否存在回文串。期望得分
分。
：显然每个位置上的数只需要和前一个位置不同即可，后
个位置每个位置都有
种替换方案，所以方案总数为
。
：暗（
明）示正解思路，考虑在两边有限制的情况下的方案数，显然两边有数分为两种情况：数字相同和数字不同。设状态为，表示数列除两边非零的数外，中间
的个数为
。对于
，
为两边数字不同，
为两边数字相同。那么考虑转移方程：
- 初始状态
。
- 当两边的数相同时，考虑填
个
时的情况，由于填
个
，即
。
- 当两边的数不同时，由于填
，当
时，有
种方案，当
且
时，有
种方案，即
。
所以跑DP就行了，复杂度。
题目思路
参考的思路，先完成
，一个数列不存在长度
且为偶数的回文子数列当且仅当一个数列不存在相邻两个相等的数（否则构成长度为
的回文子数列）。对于一般的数据，可以视为多组
数据的叠加，所以不妨先跑一遍DP，首尾连续的
可以视为
的情况，数列中间的两个数之间有
可以视为
的情况，至此可以解决
的所有情况。
类似的，对于，我们不难发现，一个数列不存在长度
且为奇数的回文子数列当且仅当一个数列不存在
的情况（否则构成长度为
的回文子数列）。所以可以把奇数位和偶数位拆开考虑，得到两个
问题。至此，问题完全解决。
考察知识点
DP。
代码实现
//Author:BLUESKY007
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5,MOD=998244353;
int n,k,mood;
int a[N],cnto,cnte;
int odst,oden,evst,even,od[N],ev[N];
long long f[2][N],ans=1;//same/amount of -1
long long plu(long long u,long long v){
return (u+v)%MOD;
}
long long mul(long long u,long long v){
return u*v%MOD;
}
long long qpow(long long u,int v){
long long rep=1;
while(v>0){
if(v&1){
rep=rep*u%MOD;
}
u=u*u%MOD;
v>>=1;
}
return rep;
}
char in[20],out[20];
int main(){
ans=1;
memset(f,0,sizeof f);
cnto=0;cnte=0;
odst=oden=evst=even=0;
scanf("%d%d%d",&n,&k,&mood);
if(mood){
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
if(i&1){
od[++cnto]=a[i];
}
else{
ev[++cnte]=a[i];
}
}
f[0][0]=1;
od[cnto+1]=-1;
ev[cnte+1]=-1;
for(int i=1;i<=n;i++){
if(i&1){
f[0][i]=plu(mul(2,mul(f[0][i>>1],f[1][i>>1])),mul(k-2,mul(f[0][i>>1],f[0][i>>1])));
f[1][i]=plu(mul(f[1][i>>1],f[1][i>>1]),mul(k-1,mul(f[0][i>>1],f[0][i>>1])));
}
else{
f[0][i]=plu(f[1][i-1],mul(k-2,f[0][i-1]));
f[1][i]=mul(k-1,f[0][i-1]);
}
}
odst=1;oden=cnto;
evst=1;even=cnte;
for(int i=1;i<=cnto+1;i++){
if(od[i]!=0){
odst=i;
break;
}
}
if(odst>cnto){
ans=mul(ans,mul(k,qpow(k-1,cnto-1)));
}
else{
for(int i=cnto;~i;i--){
if(od[i]!=0){
oden=i;
break;
}
}
ans=mul(ans,qpow(k-1,odst-1+cnto-oden));
for(int i=odst+1,lst=odst;i<=oden;i++){
if(od[i]!=0){
if(od[i]==od[lst]){
ans=mul(ans,f[1][i-lst-1]);
}
else{
ans=mul(ans,f[0][i-lst-1]);
}
lst=i;
}
}
}
for(int i=1;i<=cnte+1;i++){
if(ev[i]!=0){
evst=i;
break;
}
}
if(evst>cnte){
ans=mul(ans,mul(k,qpow(k-1,cnte-1)));
}
else{
for(int i=cnte;~i;i--){
if(ev[i]!=0){
even=i;
break;
}
}
ans=mul(ans,qpow(k-1,evst-1+cnte-even));
for(int i=evst+1,lst=evst;i<=even;i++){
if(ev[i]!=0){
if(ev[i]==ev[lst]){
ans=mul(ans,f[1][i-lst-1]);
}
else{
ans=mul(ans,f[0][i-lst-1]);
}
lst=i;
}
}
}
printf("%lld\n",ans);
}
else{
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
od[++cnto]=a[i];
}
f[0][0]=1;
od[cnto+1]=-1;
for(int i=1;i<=n;i++){
if(i&1){
f[0][i]=plu(mul(2,mul(f[0][i>>1],f[1][i>>1])),mul(k-2,mul(f[0][i>>1],f[0][i>>1])));
f[1][i]=plu(mul(f[1][i>>1],f[1][i>>1]),mul(k-1,mul(f[0][i>>1],f[0][i>>1])));
}
else{
f[0][i]=plu(f[1][i-1],mul(k-2,f[0][i-1]));
f[1][i]=mul(k-1,f[0][i-1]);
}
}
odst=1;oden=cnto;
for(int i=1;i<=cnto+1;i++){
if(od[i]!=0){
odst=i;
break;
}
}
if(odst>cnto){
ans=mul(ans,mul(k,qpow(k-1,cnto-1)));
}
else{
for(int i=cnto;~i;i--){
if(od[i]!=0){
oden=i;
break;
}
}
ans=mul(ans,qpow(k-1,odst-1+cnto-oden));
for(int i=odst+1,lst=odst;i<=oden;i++){
if(od[i]!=0){
if(od[i]==od[lst]){
ans=mul(ans,f[1][i-lst-1]);
}
else{
ans=mul(ans,f[0][i-lst-1]);
}
lst=i;
}
}
}
printf("%lld\n",ans);
}
return 0;
}
T3 分班问题
解题思路
sub1
:
模数暗示做法 怎么暴力怎么来。
sub2
:显然答案为
暴力计算时间复杂度
sub3
我们考虑上面40pts的式子，显然暴力运算已经不可取了，因为和
都非常大。
我们考虑对这个组合数进行恒等变化。为了方便运算，接著下面两个引理。
引理1
考虑如何证明：显然它是有组合意义的：在第一堆个物品中选若干个，另一堆
个物品中选若干个，使得选择的个数之和等于
，那么他显然等于在一堆
个中任意选
个的方案数，证毕。
引理2
考虑如何证明：显然(这是一个最基础的的组合数恒等式),此时我们发现
符合引理1的格式，直接代入得到答案,证毕。
借助引理推导
我们考虑我们需要计算的数： 这个式子并不是简单的两个组合数相乘，他带着一个变量
导致我们难以计算，我们想办法把
"吸收进去".
我们考虑组合数的通项公式，那么我们观察到
与他们的下指标相同，我们就有
此时我们代入引理2可以得到
预处理组合数可以计算。
时间复杂度
sub4
我们无法预处理组合数，因为太大了，我们观察到19260817是一个
暴力素数。
我们采用Lucas定理可以做到
考察知识点
组合数恒等变换，Lucas定理。
代码实现
//Author:Venn
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn = 2e7+10,p=19260817;
int inc(int a,int b) {
a+=b;
return a>=p?a-p:a;
}
int dec(int a,int b) {
a-=b;
return a<0?a+p:a;
}
int mul(int a,int b) {
return int(1LL*a*b%p);
}
int qpow(int a,int b) {
int ret = 1;
while(b) {
if(b&1) ret=mul(ret,a);
a=mul(a,a);
b>>=1;
}
return ret;
}
int fac[maxn],ifac[maxn];
void init() {
fac[0]=1;
for(int i=1;i<p;++i) fac[i] = mul(fac[i-1],i);
ifac[p-1] = qpow(fac[p-1],p-2);
for(int i = p-2;i>=0;--i) ifac[i]=mul(ifac[i+1],i+1);
}
int C(int a,int b) {
if(b<0) return 0;
if(a<b) return 0;
return mul(fac[a],mul(ifac[a-b],ifac[b]));
}
int Lucas(ll a,ll b) {
if(a<=p&&b<=p) {
return C(int(a),int(b));
}
return mul(C(int(a%p),int(b%p)),Lucas(a/p,b/p));
}
int T;
ll n,m;
int main() {
init();
scanf("%d",&T);
while(T--) {
scanf("%lld%lld",&n,&m);
printf("%d\n",mul(mul(int(m%p),Lucas(n+m-1,n-1)),2) );
}
return 0;
}
