电脑卡死了然后所有东西都没了，我只能蚌。那重写吧。
最近确实感觉挺降智的，许多挺直觉的东西都想不起来了。不知道是不是太情绪化了的影响。
见识了 H_Kaguya 的哈希写法。他的哈希是 \(hs_i=hs_{i-1}+s_ip^i\)。
才发现博客园个人页面右下角有个回到页首。
硬币序列
赛时基本会了，但是有一步假了结果挂成 20。又垫了，菜死了。
首先考虑看上去的一个 \(O(n^3)\) dp，不再详说。
然后猜一下这个长度是可以二分的。感性理解一下二分之后 \(0\) 的个数是一段区间。于是可以二分这个区间是否包含 \(a\)。
然后考虑构造。得到 \(0\) 的个数区间之后容易跟着 dp 一起算出最小值和最大值的方案。然后取一个最小值的前缀和最大值的后缀一定可以得到。证明考虑每次 \(0\) 的个数最多 \(\pm 1\)，要从最大值到最小值一定经过中间所有值。而衔接位置字符相同的同理可以直接忽略。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <list>
using namespace std;
int n,a,b,dp[1000010][2],sum[1000010];
pair<int,int>pre[100010][2];
int q1[1000010],l1,r1,q2[1000010],l2,r2;
char s[1000010],s1[1000010],s2[1000010],t[1000010];
pair<int,int>check(int k){
l1=l2=r1=r2=1;q1[1]=q2[1]=0;
for(int i=1;i<=n;i++){
dp[i][0]=dp[i][1]=n+1;
while(l1<=r1&&q1[l1]<i-k)l1++;
while(l2<=r2&&q2[l2]<i-k)l2++;
if(s[i]!='1')if(l1<=r1)dp[i][0]=dp[q1[l1]][1]+(sum[i]-sum[q1[l1]]),pre[i][0]=make_pair(q1[l1],1);
if(s[i]!='0')if(l2<=r2)dp[i][1]=dp[q2[l2]][0],pre[i][1]=make_pair(q2[l2],0);
while(l2<=r2&&dp[q2[r2]][0]>=dp[i][0])r2--;
while(l1<=r1&&dp[q1[r1]][1]-sum[q1[r1]]>=dp[i][1]-sum[i])r1--;
if(s[i]=='0')r2=l2-1;
if(s[i]=='1')r1=l1-1;
if(s[i]!='1')q2[++r2]=i;
if(s[i]!='0')q1[++r1]=i;
}
int mn=min(dp[n][0],dp[n][1]);
if(mn==dp[n][0]){
pair<int,int>p=make_pair(n,0);
while(p.first>0){
pair<int,int> p1=pre[p.first][p.second];
for(int i=p1.first+1;i<=p.first;i++)s1[i]=p.second+'0';
p=p1;
}
}
else{
pair<int,int>p=make_pair(n,1);
while(p.first>0){
pair<int,int> p1=pre[p.first][p.second];
for(int i=p1.first+1;i<=p.first;i++)s1[i]=p.second+'0';
p=p1;
}
}
l1=l2=r1=r2=1;q1[1]=q2[1]=0;
for(int i=1;i<=n;i++){
dp[i][0]=dp[i][1]=-1;
while(l1<=r1&&q1[l1]<i-k)l1++;
while(l2<=r2&&q2[l2]<i-k)l2++;
if(s[i]!='1')if(l1<=r1)dp[i][0]=dp[q1[l1]][1]+(sum[i]-sum[q1[l1]]),pre[i][0]=make_pair(q1[l1],1);
if(s[i]!='0')if(l2<=r2)dp[i][1]=dp[q2[l2]][0],pre[i][1]=make_pair(q2[l2],0);
while(l2<=r2&&dp[q2[r2]][0]<=dp[i][0])r2--;
while(l1<=r1&&dp[q1[r1]][1]-sum[q1[r1]]<=dp[i][1]-sum[i])r1--;
if(s[i]=='0')r2=l2-1;
if(s[i]=='1')r1=l1-1;
if(s[i]!='1')q2[++r2]=i;
if(s[i]!='0')q1[++r1]=i;
}
int mx=max(dp[n][0],dp[n][1]);
if(mx==dp[n][0]){
pair<int,int>p=make_pair(n,0);
while(p.first>0){
pair<int,int> p1=pre[p.first][p.second];
for(int i=p1.first+1;i<=p.first;i++)s2[i]=p.second+'0';
p=p1;
}
}
else{
pair<int,int>p=make_pair(n,1);
while(p.first>0){
pair<int,int> p1=pre[p.first][p.second];
for(int i=p1.first+1;i<=p.first;i++)s2[i]=p.second+'0';
p=p1;
}
}
return make_pair(mn,mx);
}
int sum1[1000010],sum2[1000010];
void getans(int mid){
check(mid);
for(int i=1;i<=n;i++){
sum1[i]=sum1[i-1];
if(s[i]=='?')sum1[i]+=(s1[i]=='0');
}
for(int i=n;i>=1;i--){
sum2[i]=sum2[i+1];
if(s[i]=='?')sum2[i]+=(s2[i]=='0');
}
for(int i=0;i<=n;i++){
if(s1[i]==s2[i+1])continue;
if(sum1[i]+sum2[i+1]==a){
for(int j=1;j<=i;j++)t[j]=s1[j];
for(int j=i+1;j<=n;j++)t[j]=s2[j];
return;
}
}
}
int main(){
int tim,od;scanf("%d%d",&tim,&od);
while(tim--){
scanf("%d%d%d%s",&n,&a,&b,s+1);
for(int i=1;i<=n;i++)sum[i]=sum[i-1]+(s[i]=='?');
int l=0,r=n;
while(l<r){
int mid=(l+r)>>1;
pair<int,int>p=check(mid);
if(p.second>=a&&p.first<=a)r=mid;
else l=mid+1;
}
printf("%d\n",l);
if(od)getans(l),printf("%s\n",t+1);
for(int i=0;i<=n+1;i++)s[i]=s1[i]=s2[i]=t[i]=sum1[i]=sum2[i]=sum[i]=0;
}
return 0;
}
划分线段
首先线段无交构成一棵树。那做树形 dp。
设 \(dp_{x,i,0/1,0/1}\) 为在 \(x\) 节点，选了 \(i\) 个子区间，左端点左边是否选了，右端点右边是否选了的最大贡献。转移是个树形背包合并子树。直接做是 \(O(n^3)\) 的，然而发现每个节点的背包容量是 \([size_x,2size_x]\) 的，于是就是 \(O(n^2)\) 的了。
摆大烂，不写了。
打怪升级
如果一次只加一个那就是一眼）
判无解。先考虑没有不相交的限制怎么算，然后套个 LGV。设总共加 \(t\) 次，位置 \(i\) 需要 \(d_i\)，那么就是 \(2t\) 次单点加，\(12,34\cdots\) 之间不区分顺序的方案数，即
\[\binom{2t}{d_1,d_2,\cdots,d_n}\frac 1{2^t} \]然而两次不能加到同一个上。我们枚举几次加到了同一个上然后容斥掉：设 \(i\) 位置重复加了 \(x_i\) 次：
\[\sum_{x=0}^t(-1)^s\binom ts\binom s{x_1,x_2,\cdots,x_n}\binom{2(t-s)}{d_1-2x_1,d_2-2x_2,\cdots,d_n-2x_n}\frac 1{2^t} \]把 \((-1)^s\dbinom tss!(2(t-s))!\dfrac 1{2^t}\) 提出来，可以背包，也长得像个多项式：第 \(i\) 个 \(x^j\) 项为 \(\dfrac 1{j!}\dfrac 1{(d_i-2j)!}\)。设这个是 \(F_{d_i}\)。那么 LGV 的矩阵的 \((i,j)\) 位置就是 \(F_{b_j-a_i}\)，插 \(t+1\) 个点值算行列式就行了。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
typedef vector<int> poly;
const int mod=1000000007;
int n,A[50],B[50],jc[6010],inv[6010],Inv[6010];
int C(int n,int m){
if(n<m||m<0)return 0;
return 1ll*jc[n]*inv[m]%mod*inv[n-m]%mod;
}
int qpow(int a,int b){
int ans=1;
while(b){
if(b&1)ans=1ll*ans*a%mod;
a=1ll*a*a%mod;
b>>=1;
}
return ans;
}
int x[6010],y[6010],a[50][50],g[6010];
poly f[50][50];
int calc(poly &f,int x){
int ans=0;
for(int i=0,pw=1;i<f.size();i++,pw=1ll*pw*x%mod)ans=(ans+1ll*f[i]*pw)%mod;
return ans;
}
int gauss(){
int ans=1,w=1;
for(int i=1;i<=n;i++){
int mx=i;
for(int j=i+1;j<=n;j++){
if(a[j][i]>a[mx][i])mx=j;
}
if(mx!=i){
w=-w;
for(int j=1;j<=n;j++)swap(a[i][j],a[mx][j]);
}
if(!a[i][i])return 0;
int inv=qpow(a[i][i],mod-2);
for(int j=1;j<=n;j++){
if(i==j)continue;
int rate=1ll*a[j][i]*inv%mod;
for(int k=1;k<=n;k++)a[j][k]=(a[j][k]-1ll*rate*a[i][k]%mod+mod)%mod;
}
}
for(int i=1;i<=n;i++)ans=1ll*ans*a[i][i]%mod;
ans=(ans*w+mod)%mod;
return ans;
}
int main(){
scanf("%d",&n);int t=0;jc[0]=inv[0]=Inv[1]=1;
for(int i=2;i<=6000;i++)Inv[i]=1ll*(mod-mod/i)*Inv[mod%i]%mod;
for(int i=1;i<=6000;i++)jc[i]=1ll*jc[i-1]*i%mod,inv[i]=1ll*inv[i-1]*Inv[i]%mod;
for(int i=1;i<=n;i++)scanf("%d",&A[i]);
for(int i=1;i<=n;i++)scanf("%d",&B[i]),t+=B[i]-A[i];
if(t&1){
puts("0");return 0;
}
for(int i=1;i<=n;i++){
if(A[i]>B[i]){
puts("0");return 0;
}
for(int j=1;j<=n;j++){
if(A[i]>A[j]&&B[i]<B[j]){
puts("0");return 0;
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(A[i]>B[j]){
f[i][j].push_back(0);continue;
}
for(int k=0;k<=(B[j]-A[i]>>1);k++){
f[i][j].push_back(1ll*inv[k]*inv[B[j]-A[i]-2*k]%mod);
}
}
}
t>>=1;
const int lim=t+1;
for(int x=1;x<=lim;x++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
a[i][j]=calc(f[i][j],x);
}
}
y[x]=gauss();
}
x[0]=1;
for(int i=1;i<=lim;i++){
for(int j=lim;j>=1;j--){
x[j]=(x[j-1]-1ll*i*x[j]%mod+mod)%mod;
}
x[0]=1ll*x[0]*(mod-i)%mod;
}
for(int i=1;i<=lim;i++){
static int tmp[6010];
int val=mod-Inv[i];
tmp[0]=1ll*x[0]*val%mod;
for(int j=1;j<=lim;j++)tmp[j]=1ll*val*(x[j]-tmp[j-1]+mod)%mod;
val=y[i];
for(int j=1;j<=lim;j++){
if(i==j)continue;
if(i>j)val=1ll*val*Inv[i-j]%mod;
else val=1ll*val*(mod-Inv[j-i])%mod;
}
for(int j=0;j<=lim;j++)g[j]=(g[j]+1ll*val*tmp[j])%mod;
}
int ans=0;
for(int i=0;i<=t;i++){
if(i&1)ans=(ans-1ll*C(t,i)*jc[i]%mod*jc[(t-i)<<1]%mod*g[i]%mod+mod)%mod;
else ans=(ans+1ll*C(t,i)*jc[i]%mod*jc[(t-i)<<1]%mod*g[i])%mod;
}
ans=1ll*ans*qpow(qpow(2,t),mod-2)%mod;
printf("%d\n",ans);
return 0;
}