P1054 · OFFICIAL SOLUTION

P1054 遗失的赋值官方题解

Gioush OJ · P1054 遗失的赋值

【数据点 1∼21\sim 21∼2】

这一档保证 $n\leq20$ 。枚举全部 $2^n$ 个 $01$ 序列。
对每个序列检查 $1$ 的总数与全部长度为 $k$ 的区间和，统计合法序列即可。
使用滑动窗口可以在线性时间内检查一个序列，总时间复杂度为 $\mathcal{O}(n2^n)$ 。

【性质观察】

相邻两个窗口只有最左端与新加入的最右端不同，因此

s_{i+1}-s_i=x_{i+k}-x_i.

一旦知道 $x_i$ ，就可以由窗口和之差唯一确定 $x_{i+k}$ 。
于是下标对 $k$ 取模相同的位置形成一条链，每条链只需要决定最前面的一个 $01$ 值。

【数据点 3∼53\sim 53∼5】

这一档保证 $k\leq20$ 。先在线性时间内预处理每条同余链在初值为 $0$ 或 $1$ 时是否合法，以及整条链中 $1$ 的数量。
随后枚举前 $k$ 个位置的 $2^k$ 种取值。每次只需检查 $k$ 条链，并核对 $s_1$ 与 $m$ 。
时间复杂度为 $\mathcal{O}(n+k2^k)$ ，空间复杂度为 $\mathcal{O}(n)$ 。

【数据点 6∼96\sim 96∼9】

对一条同余链分别尝试初值 $0,1$ 。若两种初值都不合法，则整组数据无解。若只有一种合法，这条链已经被确定。
若两种初值都合法，就把它称为自由链。选择初值 $1$ 会让前 $k$ 个位置中的 $1$ 增加一个，并让总数增加链长。
可以对自由链做计数 DP，记录选择了多少条链以及这些链贡献的 $1$ 的总数。
利用链长只有两种，分别对两类自由链做组合 DP，可以做到 $\mathcal{O}(n+k^2)$ 。

【数据点 10∼1510\sim 1510∼15】

这一档保证 $k\mid n$ ，所以所有同余链的长度都等于 $n/k$ 。
设已经确定的链在前 $k$ 个位置中贡献 $f$ 个 $1$ ，在整个序列中贡献 $g$ 个 $1$ 。
必须从自由链中选择 $s_1-f$ 条使用初值 $1$ ，并检查

m-g=(s_1-f)\frac{n}{k}.

若等式成立，答案就是从全部自由链中选择 $s_1-f$ 条的方案数。

【正解】

令 $h=\lfloor n/k\rfloor$ ，前 $n\bmod k$ 条同余链长度为 $h+1$ ，其余链长度为 $h$ 。

设两类自由链数量分别为 $a,b$ ，需要选择其中 $x,y$ 条使用初值 $1$ 。
根据第一段窗口和与整个序列中 $1$ 的总数，有

\begin{cases} x+y=s_1-f,\\ (h+1)x+hy=m-g. \end{cases}

因而 $x=(m-g)-h(s_1-f)$ ， $y=(s_1-f)-x$ ，答案为

\dbinom{a}{x}\dbinom{b}{y}.

【实现与复杂度】

预处理阶乘与逆阶乘，就可以在 $\mathcal{O}(1)$ 时间内计算组合数。
每个位置只会在对应同余链中被扫描一次，因此单组时间复杂度为 $\mathcal{O}(n)$ 。
组合数及最终答案均对 $998{,}244{,}353$ 取模。链中 $1$ 的总数与两个方程的右侧需要使用 long long。

【参考代码】

1/*2Author:Ehundategh3Date:2026/8/24Name:assign.cpp5You steal,I kill.6*/7#include <cstdio>8#include <cstring>9#include <algorithm>10#define MAXN 100001011using namespace std;12const int Mod=998244353;13int c,T,n,k,m,Line[MAXN],Delta[MAXN],Fac[MAXN],Inv[MAXN];14int Mul(int a,int b){return 1ll*a*b%Mod;}15int Power(int a,int b){16    int Ret=1;17    while(b){18        if(b&1) Ret=Mul(Ret,a);19        a=Mul(a,a);b>>=1;20    }21    return Ret;22}23int C(int n,long long m){24    if(m<0||m>n) return 0;25    return Mul(Fac[n],Mul(Inv[m],Inv[n-m]));26}27void Init(){28    Fac[0]=1;29    for(int i=1;i<MAXN;i++) Fac[i]=Mul(Fac[i-1],i);30    Inv[MAXN-1]=Power(Fac[MAXN-1],Mod-2);31    for(int i=MAXN-1;i>=1;i--) Inv[i-1]=Mul(Inv[i],i);32    return;33}34void Solve(){35    scanf("%d%d%d",&n,&k,&m);36    for(int i=1;i<=n-k+1;i++) scanf("%d",&Line[i]);37    for(int i=1;i<=n-k;i++){38        Delta[i]=Line[i+1]-Line[i];39        if(Delta[i]<-1||Delta[i]>1){printf("0\n");return;}40    }41    int Long=n%k,Length=n/k,FreeLong=0,FreeShort=0;42    long long First=0,Total=0;43    for(int r=1;r<=k;r++){44        int Now=0;bool Can[2]={1,1};long long Count[2]={0,0};45        for(int i=r;i<=n;i+=k){46            if(i!=r) Now+=Delta[i-k];47            for(int x=0;x<=1;x++){48                if(x+Now<0||x+Now>1) Can[x]=0;49                else Count[x]+=x+Now;50            }51        }52        if(!Can[0]&&!Can[1]){printf("0\n");return;}53        if(Can[0]&&Can[1]){54            if(r<=Long) FreeLong++;55            else FreeShort++;56        }57        else{58            int x=Can[1];59            First+=x;Total+=Count[x];60        }61    }62    long long NeedFirst=Line[1]-First,NeedTotal=m-Total;63    long long TakeLong=NeedTotal-NeedFirst*Length;64    long long TakeShort=NeedFirst-TakeLong;65    printf("%d\n",Mul(C(FreeLong,TakeLong),C(FreeShort,TakeShort)));66    return;67}68int main(){69    Init();70    scanf("%d%d",&c,&T);71    while(T-->0) Solve();72    return 0;73}