例题引入

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

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

发表评论

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

你是机器人吗? =。= *