省选武汉联测 1

数据好水。考试的时候感觉很摆，全程口胡，根本没写代码。

递归函数

场上看着这个东西寻思着一堆跳着的组合数求和怎么搞啊，推了半天单位根反演，未果，寻病终。

不是很知道他在干什么，贺了份代码。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define int long long
using namespace std;
int mod=998444353;
int n,m,b,ans1,ans;
struct node{
    int a[20][20];
    node(){memset(a,0,sizeof(a));}
    node operator*(node s){
        node ret;
        for(int i=0;i<=m;i++)for(int j=0;j<=m;j++)for(int k=0;k<=m;k++)ret.a[i][j]=(ret.a[i][j]+1ll*a[i][k]*s.a[k][j])%mod;
        return ret;
    }
}A,B,C;
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;
}
node qpow(node a,int b){
    node ans;
    for(int i=0;i<=m;i++)ans.a[i][i]=1;
    while(b){
        if(b&1)ans=ans*a;
        a=a*a;
        b>>=1;
    }
    return ans;
}
int getans(int d,int r){
    if(m==1)return 1;
    int cnt=(n-r-2+d)/d;
    return (C*qpow(A,m+r-2)*qpow(B*qpow(A,d-1),cnt)).a[0][m];
}
signed main(){
    scanf("%d%d%d",&n,&m,&b);
    C.a[0][0]=1;
    for(int i=0;i<m;i++)B.a[i][i]=B.a[i][i+1]=1;
    B.a[m][m]=1;
    A=B;A.a[m-1][m]=0;B.a[m-2][m]=1;
    if(b==6)b=3;
    if(b==10)b=5;
    if(b==2||b==3||b==5||b==7){
        for(int d=b;d<=n;d*=b)ans=(ans+getans(d,n%d))%mod;
    }
    if(b==4||b==8||b==9){
        int t1,t2;
        if(b==9)t1=3;
        else t1=2;
        if(b==8)t2=3;
        else t2=2;
        for(int d=t1;d<=n;d*=t1)ans=(ans+getans(d,n%d))%mod;
        mod=t2;
        for(int d=t1;d<=n;d*=t1)ans1=(ans1+getans(d,n%d))%mod;
        mod=998444353;
        ans=1ll*(ans-ans1+mod)%mod*qpow(t2,mod-2)%mod;
    }
    printf("%d\n",ans);
    return 0;
}

火力规划

比较智慧。CF575I。

四个情况是对称的，只讨论第一种。

首先时间，\(x\)，\(y\)，\(x+y\) 是个四维偏序。三只 \(\log\) 看起来就很过不去。然而好像有人卡过去了。

考虑一下这四维有没有什么关系。发现我们要满足 \(x'\ge x,y'\ge y,x'+y'\le x+y+r\)。那么对 \(x'\ge x,y'\ge y\) 容斥，枚举强制不满足几个条件，就是两个三维偏序，还有一个 \(x'<x,y'<y,x'+y'\le x+y+r\)。容易发现第三个条件没用，所以还是三维偏序。

四个都做一遍就行了。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int n,q,ans[100010],x[100010],y[100010],d[100010],r[100010];
struct BIT{
    int n,m,c[10010][5010];
    #define lowbit(x) (x&-x)
    void update(int x,int y,int val){
        for(int i=x;i<=n;i+=lowbit(i)){
            for(int j=y;j<=m;j+=lowbit(j)){
                c[i][j]+=val;
            }
        }
    }
    int query(int x,int y){
        int sum=0;
        for(int i=x;i;i-=lowbit(i)){
            for(int j=y;j;j-=lowbit(j))sum+=c[i][j];
        }
        return sum;
    }
    void clear(){memset(c,0,sizeof(c));}
}c;
int main(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=q;i++){
        int od;scanf("%d",&od);
        if(od==1)scanf("%d%d%d%d",&d[i],&x[i],&y[i],&r[i]);
        else scanf("%d%d",&x[i],&y[i]);
    }
    c.n=c.m=n;
    for(int i=1;i<=q;i++){
        if(d[i]==1)c.update(x[i],y[i],1),c.update(x[i],y[i]+r[i]+1,-1);
        if(d[i]==2)c.update(x[i],y[i]-r[i],1),c.update(x[i],y[i]+1,-1);
        if(d[i]==3)c.update(x[i]+1,y[i]+r[i]+1,1),c.update(x[i]+1,y[i],-1);
        if(d[i]==4)c.update(x[i]+1,y[i]+1,1),c.update(x[i]+1,y[i]-r[i],-1);
        if(!d[i])ans[i]+=c.query(x[i],y[i]);
    }
    c.clear();
    c.n=2*n;
    for(int i=1;i<=q;i++){
        if(d[i]==2)c.update(x[i]-y[i]+r[i]+n+2,y[i]+1,1),c.update(x[i]-y[i]+r[i]+n+2,y[i]-r[i],-1);
        if(d[i]==3)c.update(x[i]-y[i]-r[i]+n+1,y[i],1),c.update(x[i]-y[i]-r[i]+n+1,y[i]+r[i]+1,-1);
        if(!d[i])ans[i]+=c.query(x[i]-y[i]+n+1,y[i]);
    }
    c.clear();
    for(int i=1;i<=q;i++){
        if(d[i]==1)c.update(x[i]+y[i]+r[i]+1,n-y[i]+2,1),c.update(x[i]+y[i]+r[i]+1,n-y[i]-r[i]+1,-1);
        if(d[i]==4)c.update(x[i]+y[i]-r[i],n-y[i]+1,1),c.update(x[i]+y[i]-r[i],n-y[i]+r[i]+2,-1);
        if(!d[i])ans[i]+=c.query(x[i]+y[i],n-y[i]+1);
    }
    for(int i=1;i<=q;i++)if(!d[i])printf("%d\n",ans[i]);
    return 0;
}

再生核希尔伯特空间

根号分治。

建 AC 自动机，然后对询问串长根号分治。如果大于根号，那正常扫整个 fail 树统计答案。小于根号的，每次可以暴力统计每个节点的贡献。这部分如果用主席树多个 \(\log\)，然而实际上可以直接分块统计链和，不带 \(\log\)。

没写。