给定 \(n(n\le10^6)\)，对于 \([0,n]\) 中的每一个 \(k\)，求出有多少个长度为 \(n\) 的 \(01\) 串，其中最长 \(1\) 连续段长度恰好为 \(k\)。
由于是 \(1\) 连续段，不妨按照每个 \(0\) 把 \(01\) 串划分为 \(i+1\) 段，即串中有 \(i\) 个 \(0\)。
记 \(f_k\) 为长度为 \(n\) 的 \(01\) 串满足最长的 \(1\) 连续段长度小于等于 \(k\) 的数量。
去枚举 \(i\)，然后枚举 \(1\) 长度超过 \(k\) 连续段 \(j\) 的数量，就可以按照容斥原理计算 \(f_k\)。
\[f_k=\sum_{i=1}^n\sum_{j=0}^n(-1)^j\binom{i+1}j\binom{n-(k+1)j}i
\]
从 \(i+1\) 段 \(1\) 连续段中取 \(j\) 段长度超过 \(k\) 即为 \(\binom{i+1}j\)。
由于钦定了 \(j\) 段长度至少为 \(k\)，所以多出来的点有 \(n-(k+1)j\) 个，分成 \(i+1\) 段的方案数即为 \(\binom{n-(k+1)j}i\)。
根据杨辉三角，\(\binom{i+1}j=\binom ij+\binom i{j-1}\)。
根据结论 \(\binom xy\binom yz=\binom xz\binom{x-z}{y-z}\)，用分配率提出其中一项 \(\binom ij\) 带入原式。
\[\sum_{i=1}^n\sum_{j=0}^n(-1)^j\binom{n-(k+1)j}i\binom ij
\]
\[\sum_{i=1}^n\sum_{j=0}^n(-1)^j\binom{n-(k+1)j}j\binom{n-(k+1)j-j}{i-j}
\]
左边的组合数与 \(i\) 无关。右边的组合数中上面与 \(i\) 无关，下面可以取到任意有效值，所以这些所有有效值加起来就是杨辉三角第 \(n-(k+1)j-j\) 层之和 \(2^{n-(k+1)j-j}\)。
\[\sum_{j=0}^n(-1)^j2^{n-(k+1)j-j}\binom{n-(k+1)j}j
\]
注意到只有 \(n-(k+1)j\ge0\) 时组合数才有意义。
\[\sum_{j=0}^{\lfloor\frac n{k+1}\rfloor}(-1)^j2^{n-(k+1)j-j}\binom{n-(k+1)j}j
\]
同理把另一项 \(\binom i{j-1}\) 带入化简。
\[\sum_{j=0}^{\lfloor\frac n{k+1}\rfloor}(-1)^j2^{n-(k+1)j-(j-1)}\binom{n-(k+1)j}{j-1}
\]
\[f_k=\sum_{j=0}^{\lfloor\frac n{k+1}\rfloor}(-1)^j(2^{n-(k+1)j-j}\binom{n-(k+1)j}j+2^{n-(k+1)j-(j-1)}\binom{n-(k+1)j}{j-1})
\]
注意做出来的 \(f_k\) 是最长 \(1\) 连续段长度不超过 \(k\) 的方案数，而题目要求的是恰好为 \(k\) 的方案数，所以 \(ans_k=f_k-f_{k-1}\)。
由于对于每个 \([1,n]\) 的 \(k\) 都要做，所以总复杂度是 \(\mathcal O(\sum_{i=1}^n\frac ni)=\mathcal O(n\log n)\)。（预处理组合数，\(2\) 的幂）
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cassert>
#include<ctime>
#include<random>
#if __cplusplus>=202002L
#include<ranges>
namespace vw=std::views;
#endif
#define siz(x) int((x).size())
#define cauto const auto
#define elif else if
#define all(x) std::begin(x),std::end(x)
#define rall(x) std::rbegin(x),std::rend(x)
#define fi first
#define se second
#define continue(x...) {x;continue;}
#define break(x...) {x;break;}
#define debug(x) #x" "<<(x)
#define memor(x) #x" "<<1.*sizeof(x)/1024/1024<<"MB"
using std::cin;using std::cout;
using std::max;using std::min;
using std::cerr;using std::clog;
using unt=unsigned;
using loli=long long;
using lolu=unsigned long long;
using pii=std::pair<int,int>;
using tiii=std::tuple<int,int,int>;
using bsi=std::basic_string<int>;
using bsc=std::string;
#if __cplusplus>=201402L
using std::operator""s;
#endif
#if __SIZEOF_POINTER__>=8
using venti=__int128_t;
using ventu=__uint128_t;
constexpr venti operator""_vt(lolu x){return venti(x);}
constexpr ventu operator""_uvt(lolu x){return ventu(x);}
#endif
template<typename T1,typename T2>constexpr T1&cmin(T1&x,T2&&y){if(y<x)x=y;return x;}
template<typename T1,typename T2>constexpr T1&cmax(T1&x,T2&&y){if(x<y)x=y;return x;}
template<typename T1,typename T2,typename...args>constexpr T1&cmin(T1&x,T2&&y,args&&...z){if(y<x)x=y;return cmin(x,std::forward<args>(z)...);}
template<typename T1,typename T2,typename...args>constexpr T1&cmax(T1&x,T2&&y,args&&...z){if(x<y)x=y;return cmax(x,std::forward<args>(z)...);}
template<typename T1,typename T2>constexpr T1 ceil(T1 x,T2 y){return x>0?(x+y-1)/y:x/y;}
template<typename T1,typename T2>constexpr T1 flor(T1 x,T2 y){return x>0?x/y:(x-y+1)/y;}
template<typename T>constexpr T&STLcls(T&x){T{}.swap(x);return x;}
[[maybe_unused]]struct{template<typename T>operator T(){T y;cin>>y;return y;}}tin;
struct _time{~_time(){cerr<<"\n\033[33;40m"<<1.*clock()/CLOCKS_PER_SEC<<"s\033[0m";}}_TM;
std::mt19937_64 rng(std::random_device{}());
constexpr int N=1e6+1,P=1e9+7;
struct mint{
int d;
mint()=default;
mint(int x):d(x){}
friend std::istream&operator>>(std::istream&x,mint&y){return x>>y.d;}
friend std::ostream&operator<<(std::ostream&x,mint y){return x<<y.d;}
friend mint operator+(mint x,mint y){return (x.d+=y.d)<P?x.d:x.d-P;}
mint&operator+=(mint z){return (d+=z.d)<P?d:d-=P,*this;}
friend mint operator-(mint x,mint y){return (x.d-=y.d)<0?x.d+P:x.d;}
mint&operator-=(mint z){return (d-=z.d)<0?d+=P:d,*this;}
friend mint operator*(mint x,mint y){return int(1ll*x.d*y.d%P);}
mint&operator*=(mint z){return d=int(1ll*d*z.d%P),*this;}
static mint qpow(int x,int y=P-2){int z=1;for(;y;y>>=1,x=int(1ll*x*x%P))if(y&1)z=int(1ll*x*z%P);return z;}
friend mint operator/(mint x,mint y){return x*=qpow(y.d);}
mint&operator/=(mint z){return (*this)*=qpow(z.d);}
friend mint operator^(mint x,mint y){return qpow(x.d,y.d);}
mint&operator^=(mint z){return *this=qpow(d,z.d);}
mint operator()(mint z)const{return qpow(d,z.d);}
mint&operator[](mint z){return *this=qpow(d,z.d);}
mint inv()const{return qpow(d);}
mint pow(mint z)const{return qpow(d,z.d);}
int operator+()const{return d;}
mint operator-()const{return P-d;}
int operator~()const{return ~d;}
};
mint operator""_m(lolu x){return mint(int(x%P));}
int n;
mint fac[N],inv[N],f[N],pw[N];
mint C(int x,int y){
if(x<0||y<0||x<y)return 0;
return fac[x]*inv[y]*inv[x-y];
}
signed main(){
freopen("sequence.in","r",stdin);
freopen("sequence.out","w",stdout);
std::ios::sync_with_stdio(false);cin.tie(nullptr);
cin>>n;
fac[0]=fac[1]=inv[0]=inv[1]=pw[0]=1;
for(int i=1;i<N;i++)pw[i]=pw[i-1]+pw[i-1];
for(int i=2;i<N;i++)fac[i]=fac[i-1]*i;
inv[N-1]=fac[N-1].inv();
for(int i=N-2;i>=2;i--)inv[i]=inv[i+1]*(i+1);
for(int k=0;k<=n;k++)for(int j=0;j*(k+1)<=n;j++){
if(n-(k+1)*j-(j-1)>=0){
mint sum=C(n-(k+1)*j,j-1)*pw[n-(k+1)*j-(j-1)];
if(j&1)f[k]-=sum;else f[k]+=sum;
}
if(n-(k+1)*j-j>=0){
mint sum=C(n-(k+1)*j,j)*pw[n-(k+1)*j-j];
if(j&1)f[k]-=sum;else f[k]+=sum;
}
}
for(int k=n;k>=1;k--)f[k]-=f[k-1];
for(int k=0;k<=n;k++)cout<<f[k]<<' ';
return 0;
}