例题引入

CLG 是一个喜欢打篮球的人,他身体强壮,球技高超,成为了学校篮球队的队长。
为了锻炼腿部肌肉的力量,CLG 每天都在做跳台阶的锻炼。他每次从地面(第 0 级台阶)开始,他会每一步往上跳若干级台阶,直到跳上 n 级台阶后才会休息。由于他比较奇葩,所以他每次只会跳特定的台阶数量,比如当他选择 2,3,5 的时候,他每一步只会往上跳 2 级台阶,3 级台阶或者 5 级台阶。
一段为期为 T 天的跳台阶训练开始了,闲得发慌的 CLG 找到了你,想让你求出,如果他第 i 天跳正好 $n_i$级台阶,有多少种不同的方案呢?两种方案不同当且仅当跳的次数不同或者某一次跳的台阶数不同。由于他非常非常的闲,所以他给你的 $n_i$是一个 k 进制数。
你对于他这种行为表示抗议,所以你只告诉他答案对 64123 取模的余数。
数据范围:
T 表示 CLG 训练的天数,k 表示 CLG 告诉你的台阶数量的进制数,m 表示 CLG 可能会选择的跳的台阶数,$p_i$表示 CLG 可能一次会跳的台阶数,$n_i$表示 CLG 每天训练要跳的台阶数(k 进制)
$t \leq 200$,$k \leq 10$,$m \leq 20$,$p_i \leq 20$
$n_i$的位数$\leq 1000$
没错,CLG 真的身体非常强壮。
时限 2s。

题目分析

构建矩阵

由于数据范围太大了,所以不矩阵快速幂是行不通的。
如何构建矩阵?
我们注意到此题的状态转移应为 $f(x)=\sum f(x-p_i)$,而 $p_i$的数据范围非常小,所以我们可以开一个 1×20 的矩阵 ans 表示后 20 的答案,初始 ans(0,19)=1(代表 $f(0)$)
然后我们需要一个转移矩阵 t。我们每次把 $f(x)$所在的位置从 ans(0,19)改成 ans(0,18),而 ans(0,19)这个位置给 $f(x+1)$,因此我们的转移矩阵中 $t(i+1,i)=1$(这样所有的数可以 “上移” 一位)
另外就是单独求出新的 $f(x+1)$了,根据转移方程,我们只要让转移矩阵的 $t(20-p_i,20)=1$即可。
然后我们要让答案矩阵乘以 $n_i$次转移矩阵,这个可以用矩阵快速幂实现。

矩阵快速幂

我们都知道,2 进制下的快速幂是这样的:
比如要求 10110 次幂(二进制):
这个位是从后往前算的。
第一位是 0,t 自乘一次。
第二位是 1,ans 乘一次 t,t 自乘一次。
第三位是 1,ans 乘一次 t,t 自乘一次。
第四位是 0,t 自乘一次。
第五位是 1,ans 乘一次 t,t 自乘一次。

而 k 进制,如十进制下的(并不快速的)幂:
要求 233
第一位是 3,ans 乘 3 次 t,t 自乘一次。
第二位是 3,ans 乘 3 次 t,t 自乘一次。
第三位是 2,ans 乘 2 次 t,t 自乘一次。

答案求解

我们这样存答案:
开一个 vector 数组,v(i,j) 表示第 i 位是数字 j 的询问有哪些。
然后在处理 t 的时候处理 v(i,j) 即可 (详见代码里的 work 函数)

常数优化

首先,用 struct 比用 class 和数组都快。
然后多写几个 register int
然后模数用 define 定义比用 const int 快,并且用 int 定义的话会出现两倍常数。
用 int 是比用 long long 快的,会爆 int 时强制转成 long long 即可。
以上。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define LL long long
#define ri register int
#define mod 64123
int T,m,K,mxl,mx;
struct node{int n,m,a[22][22];}ans[10005],x,tmp;
int p[22];
vector<int> v[1005][10];
char s[1005];
node operator * (node as,node bs) {
    node c;c.n=as.n,c.m=bs.m;
    for(ri i=0;i<c.n;++i)
        for(ri j=0;j<c.m;++j) {
        c.a[i][j]=0;
        for(ri k=0;k<c.m;++k)
            c.a[i][j]=(c.a[i][j]+1LL*as.a[i][k]*bs.a[k][j])%mod;
    }
    return c;
}
void work() {
    for(ri i=1;i<=mxl;++i) {
        tmp.n=x.n,tmp.m=x.m;
        for(ri j=0;j<tmp.n;++j)
            for(ri k=0;k<tmp.m;++k) tmp.a[j][k]=(j==k);
        for(ri j=0;j<K;++j) {
            for(ri k=0;k<v[i][j].size();++k) ans[v[i][j][k]]=ans[v[i][j][k]]*tmp;
            tmp=tmp*x;
        }
        x=tmp;
    }
}
int main()
{
    freopen("training.in","r",stdin);
    freopen("training.out","w",stdout);
    scanf("%d%d%d",&T,&K,&m);
    for(ri i=1;i<=m;++i) scanf("%d",&p[i]),mx=max(mx,p[i]);
    x.n=mx,x.m=mx;
    for(ri i=0;i<mx-1;++i) x.a[i+1][i]=1;
    for(ri i=1;i<=m;++i) ++x.a[mx-p[i]][mx-1];
    for(ri i=1;i<=T;++i) {
        scanf("%s",s);
        int l=strlen(s);mxl=max(mxl,l);
        for(ri j=0;j<l;++j) v[l-j][s[j]-'0'].push_back(i);
        ans[i].n=1,ans[i].m=mx,ans[i].a[0][mx-1]=1;
    }
    work();
    for(ri i=1;i<=T;++i) printf("%d\n",ans[i].a[0][mx-1]);
    return 0;
}
分类: 文章

litble

苟...苟活者在淡红的血色中,会依稀看见微茫的希望

0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注