迷惑，开三道题发现 T3 见过原题没做。然后在 kai586123 老师课件里边找到了这题题号。震撼，震撼。
不知道 NJU 营春测卡多少分。
第一题
正解是把询问对列分治，然后考虑跨过中间列的询问。
暴力 \(O(\dfrac{n^4}w+q)\) 的方法是显然的，可以获得 \(50-100\) 分不等，略微卡常后通过。
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <bitset>
using namespace std;
int n,m,Q,num,id[510][510];
char s[510][510];
bool ans[1000010];
bitset<510>f[510][510];
struct node{
pair<int,int>u,v;
int id;
};
vector<node>q[510];
void tuopu(int id){
for(int i=id;i<=n;i++)for(int j=1;j<=m;j++)f[i][j].reset();
for(int j=1;j<=m;j++)f[id][j][j]=1;
for(int i=id;i<=n;i++){
for(int j=1;j<=m;j++){
if(s[i][j]=='1')continue;
if(s[i+1][j]=='0')f[i+1][j]|=f[i][j];
if(s[i][j+1]=='0')f[i][j+1]|=f[i][j];
}
}
}
int main(){
scanf("%d%d%d",&n,&m,&Q);
for(int i=1;i<=n;i++)scanf("%s",s[i]+1);
for(int i=1;i<=Q;i++){
int x1,x2,y1,y2;scanf("%d%d%d%d",&x1,&x2,&y1,&y2);
node ret={make_pair(x1,y1),make_pair(x2,y2),i};
q[x1].push_back(ret);
}
for(int i=1;i<=n;i++){
if(q[i].empty())continue;
tuopu(i);
for(node p:q[i]){
if(f[p.v.first][p.v.second][p.u.second])ans[p.id]=true;
}
}
for(int i=1;i<=Q;i++)puts(ans[i]?"Yes":"No");
return 0;
}
第二题
题面说的对。
考虑在中间合并两边，那两边一定是一堆指向中间的链，且链数相差不超过 \(1\)。于是对前缀做一遍 dp，对后缀再做一遍，乘两个阶乘合并，如果链数相等还要乘 \(2\)。
以从前往后 dp 为例。设 \(dp_{i,j}\) 为到 \(i\) 有 \(j\) 条链的方案数，转移考虑这一位是什么：
>：两种情况：新建一条链 \(dp_{i-1,j-1}\)，并在另一条链的末尾 \(j\times dp_{i-1,j}\)。<：两种情况：作为一条链开头 \(j\times dp_{i-1,j}\)，合并两条链 \(j(j-1)\times dp_{i-1,j+1}\)。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int mod=1000000007;
int n,jc[5010],f[5010][5010],g[5010][5010];
char s[5010];
int C(int n){
return (1ll*n*(n-1)>>1)%mod;
}
int main(){
scanf("%s",s+1);n=strlen(s+1);jc[0]=1;
for(int i=1;i<=n;i++)jc[i]=1ll*jc[i-1]*i%mod;
f[0][0]=1;
for(int i=1;i<=n;i++){
if(s[i]=='>'){
for(int j=1;j<=n;j++){
f[i][j]=(f[i][j]+f[i-1][j-1])%mod;
f[i][j]=(f[i][j]+1ll*j*f[i-1][j])%mod;
}
}
else{
for(int j=1;j<=n;j++){
f[i][j]=(f[i][j]+1ll*j*f[i-1][j])%mod;
f[i][j]=(f[i][j]+2ll*C(j+1)*f[i-1][j+1])%mod;
}
}
}
g[n+1][0]=1;
for(int i=n;i>=1;i--){
if(s[i]=='<'){
for(int j=1;j<=n;j++){
g[i][j]=(g[i][j]+g[i+1][j-1])%mod;
g[i][j]=(g[i][j]+1ll*j*g[i+1][j])%mod;
}
}
else{
for(int j=1;j<=n;j++){
g[i][j]=(g[i][j]+1ll*j*g[i+1][j])%mod;
g[i][j]=(g[i][j]+2ll*C(j+1)*g[i+1][j+1])%mod;
}
}
}
for(int i=1;i<=n;i++){
int ans=0;
for(int j=0;j<=n;j++){
int ret=1ll*jc[j]*jc[j+1]%mod;
int val=(1ll*f[i-1][j]*g[i+1][j+1]+1ll*f[i-1][j+1]*g[i+1][j])%mod;
ans=(ans+1ll*ret*val)%mod;
ans=(ans+2ll*jc[j]*jc[j]%mod*f[i-1][j]%mod*g[i+1][j])%mod;
}
printf("%d ",ans);
}
puts("");
return 0;
}
第三题
原题 CF923E，这好像是场 ACM，赛时过了 300 队。
首先每次操作是把 \(f_i\) 变成 \(\sum_{j=i}^n\frac{f_j}{j+1}\)。然后写成生成函数的形式就是
\[\begin{aligned} &G(x)=\sum_{i=0}^nx^i\sum_{j=i}^n\frac{f_j}{j+1}\\ =&\sum_{j=0}^n\frac{f_j}{j+1}\sum_{i=0}^jx^i\\ =&\frac 1{1-x}\sum_{j=0}^n\frac{f_j}{j+1}(1-x^{j+1})\\ =&\frac 1{1-x}\int_x^1F(z)\text dz \end{aligned} \]这个积分的上界是个 \(1\) 很 \(2\sqrt 2\)，给他怼成 \(0\)。设个 \(P(x)=F(x+1)\)，就有了
\[\begin{aligned} G(x)&=\frac 1{1-x}\int_x^1F(z)\text dz\\ &=\frac 1{1-x}\int_{x-1}^0P(z)\text dz\\ &=\frac 1{x-1}\int_0^{x-1}P(z)\text dz \end{aligned} \]这时候思路大概很明显了。设 \(Q(x)=G(x+1)\)：
\[Q(x)=\frac 1x\int P(z)\text dz \]那显然 \([x^i]Q(x)=\frac 1{i+1}[x^i]P(x)\)。于是就是两次多项式平移。
存在手解矩阵对角化方法，但我不会线性代数。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
const int mod=998244353;
#define add(x,y) (x+y>=mod?x+y-mod:x+y)
#define sub(x,y) (x-y<0?x-y+mod:x-y)
typedef vector<int> poly;
int wl;
void get(int n){
wl=1;
while(wl<n)wl<<=1;
}
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 jc[300010],inv[300010],Inv[300010],w[300010];
void init(int n){
int t=1;
while((1<<t)<n)t++;
t=min(t-1,21);
w[0]=1;w[1<<t]=qpow(31,1<<21-t);
for(int i=t;i>=1;i--)w[1<<i-1]=1ll*w[1<<i]*w[1<<i]%mod;
for(int i=1;i<(1<<t);i++)w[i]=1ll*w[i&i-1]*w[i&-i]%mod;
jc[0]=Inv[0]=inv[1]=1;
for(int i=2;i<=n;i++)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
for(int i=1;i<=n;i++)jc[i]=1ll*jc[i-1]*i%mod,Inv[i]=1ll*Inv[i-1]*inv[i]%mod;
}
inline void DIF(poly &a){
int n=a.size();
for(int mid=n>>1;mid>=1;mid>>=1){
for(int i=0,k=0;i<n;i+=mid<<1,k++){
for(int j=0;j<mid;j++){
int x=a[i+j],y=1ll*a[i+j+mid]*w[k]%mod;
a[i+j]=add(x,y);a[i+j+mid]=sub(x,y);
}
}
}
}
inline void DIT(poly &a){
int n=a.size();
for(int mid=1;mid<n;mid<<=1){
for(int i=0,k=0;i<n;i+=mid<<1,k++){
for(int j=0;j<mid;j++){
int x=a[i+j],y=a[i+j+mid];
a[i+j]=add(x,y);a[i+j+mid]=1ll*sub(x,y)*w[k]%mod;
}
}
}
int inv=qpow(n,mod-2);
for(int i=0;i<n;i++)a[i]=1ll*a[i]*inv%mod;
reverse(a.begin()+1,a.end());
}
inline poly operator*(poly f,poly g){
int n=f.size(),m=g.size();
get(n+m);
f.resize(wl),g.resize(wl);
DIF(f);DIF(g);
for(int i=0;i<wl;i++)f[i]=1ll*f[i]*g[i]%mod;
DIT(f);
f.resize(n+m-1);
return f;
}
inline poly move(poly a,int k){
int n=a.size();get(n<<1);
poly b(n);
for(int i=0,pw=1;i<n;i++,pw=1ll*pw*k%mod){
a[i]=1ll*a[i]*jc[i]%mod;
b[i]=1ll*Inv[i]*pw%mod;
}
reverse(a.begin(),a.end());
a=a*b;a.resize(n);
reverse(a.begin(),a.end());
for(int i=0;i<n;i++)a[i]=1ll*a[i]*Inv[i]%mod;
return a;
}
int n;
long long m;
int main(){
scanf("%d%lld",&n,&m);m%=mod-1;n++;init(n<<1);
poly a(n);
for(int i=0;i<n;i++)scanf("%d",&a[i]);
a=move(a,1);
for(int i=0;i<n;i++)a[i]=1ll*a[i]*qpow(inv[i+1],m)%mod;
a=move(a,mod-1);
for(int i=0;i<n;i++)printf("%d ",a[i]);puts("");
return 0;
}