tetris

题意

给定 7 中俄罗斯方块，每种均可旋转，求恰好铺满 2\times n 格子的方案数。

思路

观察到若使用了后两种方块则必定无解，使用前四种可分 7 中情况讨论，其中两种可以无限延伸。设 f(i) 表示填满前 i 列的方案数，则 f(n) 可以用矩阵快速幂求出。

代码

#include <cstdio>
#include <cstring>
typedef long long ll;
const int MAXN=5;
const int MOD=1E9+7;
struct Matrix
{
    int n, m;
    int a[MAXN][MAXN];
    Matrix(int r=0, int c=0): n(r), m(c)
    {
        memset(a, 0, sizeof a);
    }
    Matrix operator * (const Matrix& b) const
    {
        Matrix c(n, b.m);
        for (int i=0; i<n; i++)
            for (int k=0; k<m; k++)
                for (int j=0; j<b.m; j++)
                    c.a[i][j]=(c.a[i][j]+1ll*a[i][k]*b.a[k][j])%MOD;
        return c;
    }
    Matrix operator ^ (ll k) const
    {
        Matrix s(n, m), t=*this;
        for (int i=0; i<n; i++) s.a[i][i]=1;
        while (k)
        {
            if (k&1) s=s*t;
            t=t*t; k>>=1;
        }
        return s;
    }
};
int main()
{
//  freopen("tetris.in", "r", stdin);
//  freopen("tetris.out", "w", stdout);
    ll n;
    Matrix w(3, 3), r;
    w.a[0][0]=1; w.a[0][1]=1; w.a[0][2]=0;
    w.a[1][0]=3; w.a[1][1]=0; w.a[1][2]=1;
    w.a[2][0]=2; w.a[2][1]=0; w.a[2][2]=1;
    while (~scanf("%lld", &n))
    {
        if (n&1) puts("0");
        else if (n==2) puts("1");
        else if (n==4) puts("4");
        else
        {
            r=w^(n/2);
            printf("%d\n", r.a[0][0]);
        }
    }
    return 0;
}

tab

题意

给定一个长度为 n(n\leq 10^5) 的正整数序列 a ，维护以下三种操作：

• 单点修改
• 给定正整数 y ，求 \sum_{i=1}^n\frac{y}{a_i}+y\mod a_i

思路

对于每个 y ，它除以任意正整数的余数只有 O(\sqrt y) 中取值。考虑对 y 整除分块，前缀和维护一段权值区间内 a_i 的出现次数和总和。观察到每次修改对这个前缀和有 1 次操作，而每次询问会有 O(\sqrt y) 次查询，因此可以分块来维护前缀和，做到 O(\sqrt n) 修改，O(1) 查询。总时间复杂度 O(q(\sqrt n+\sqrt y)) 。

代码

#include <cstdio>
#include <cstring>
typedef long long ll;
const int MAXN=110000;
const int MAXM=220000;
const int M=200000;
const int MAXS=550;
const int S=400, C=M/S;
struct Node
{
    int c; ll s;
    Node(): c(0), s(0) {}
    Node(int a, ll b): c(a), s(b) {}
    Node operator + (const Node& rhs)
    {
        return Node(c+rhs.c, s+rhs.s);
    }
};
struct Block
{
    Node h, v[MAXS];
} b[MAXS];
int n, q, a[MAXN];
int bl[MAXM], pos[MAXM];
int c[MAXM]; ll s[MAXM];
void init()
{
    memset(b, 0, sizeof b);
    for (int i=1; i<=M; i++) bl[i]=(i-1)/S+1, pos[i]=(i-1)%S+1;
    for (int i=1; i<=n; i++) c[a[i]]++, s[a[i]]+=a[i];
    int cur, siz; ll sum;
    for (int i=1; i<=M; i++)
    {
        if (bl[i]!=bl[i-1])
        {
            b[bl[i]].h=b[bl[i-1]].h+b[bl[i-1]].v[S];
            cur=0; siz=0; sum=0;
        }
        siz+=c[i]; sum+=s[i];
        b[bl[i]].v[++cur]=Node(siz, sum);
    }
}
void change(int x, int k)
{
    c[x]+=k; s[x]+=x*k;
    int cur=(bl[x]-1)*S, siz=0; ll sum=0;
    for (int i=1; i<=S; i++)
    {
        cur++; siz+=c[cur]; sum+=s[cur];
        b[bl[x]].v[i]=Node(siz, sum);
    }
    for (int i=bl[x]+1; i<=C; i++)
        b[i].h=b[i-1].h+b[i-1].v[S];
}
inline void update(int p, int x)
{
    change(a[p], -1);
    change(x, 1); a[p]=x;
}
inline int qsiz(int l, int r)
{
    int x=b[bl[l-1]].h.c+b[bl[l-1]].v[pos[l-1]].c;
    int y=b[bl[r]].h.c+b[bl[r]].v[pos[r]].c;
    return y-x;
}
inline ll qsum(int l, int r)
{
    ll x=b[bl[l-1]].h.s+b[bl[l-1]].v[pos[l-1]].s;
    ll y=b[bl[r]].h.s+b[bl[r]].v[pos[r]].s;
    return y-x;
}
int main()
{
//  freopen("tab.in", "r", stdin);
//  freopen("tab.out", "w", stdout);
    scanf("%d%d", &n, &q);
    for (int i=1; i<=n; i++) scanf("%d", &a[i]);
    init();
    while (q--)
    {
        int op;
        scanf("%d", &op);
        if (op==1)
        {
            int p, x;
            scanf("%d%d", &p, &x);
            update(p, x);
        }
        else
        {
            int y; ll ans=0;
            scanf("%d", &y);
            for (int l=1, r=0; l<=y; l=r+1)
            {
                int k=y/l; r=y/k;
                ans+=1ll*(k+y)*qsiz(l, r)-1ll*k*qsum(l, r);
            }
            ans+=1ll*y*qsiz(y+1, M);
            printf("%lld\n", ans);
        }

    }
    return 0;
}