题解 P5257 【密码 】
da32s1da
·
·
题解
蒟乘
答案很明显是\ \frac{(\sum x)^2-\sum x^2}{2}
设$f[i]$为$G(N)=i$的$N$的**个数**，$g[i]$为$G(N)=i$的$N$的**和**，$h[i]$为$G(N)=i$的$N$的**平方和**。
$$f[i]=\sum_{j=1}^9f[i-j]$$
$$g[i]=\sum_{j=1}^910\times g[i-j]+j\times f[i-j]$$
$$h[i]=\sum_{j=1}^9100\times h[i-j]+20j\times g[i-j]+j^2\times f[i-j]$$
放在一个矩阵里转移就好了
$$\text{答案是}\ \frac{(\sum_{i=1}^ng[i])^2-\sum_{i=1}^nh[i]}{2}$$
```cpp
#include<cstdio>
#include<cstring>
const int mod=1e6+3;
struct mat{
int c[30][30];
void clear(){memset(c,0,sizeof(c));}
mat operator *(const mat &o)const{
mat r;
r.clear();
for(int i=1;i<=29;i++)
for(int k=1;k<=29;k++)
for(int j=1;j<=29;j++)
if(c[i][k]&&o.c[k][j])
r.c[i][j]=(r.c[i][j]+1ll*c[i][k]*o.c[k][j])%mod;
return r;
}
}f,g;
int ksm(int u,int v){
int res=1;
for(;v;v>>=1,u=1ll*u*u%mod)
if(v&1)res=1ll*res*u%mod;
return res;
}
typedef long long LL;
LL n;
int main(){
scanf("%lld",&n);
f.c[1][9]=1;//f[0]=1
for(int i=1;i<=8;i++)g.c[i+1][i]=1;
for(int i=1;i<=9;i++)g.c[i][9]=1;
for(int i=10;i<=17;i++)g.c[i+1][i]=1;
for(int i=1;i<=9;i++)g.c[i][18]=10-i;
for(int i=10;i<=18;i++)g.c[i][18]=10;
for(int i=19;i<=26;i++)g.c[i+1][i]=1;
for(int i=1;i<=9;i++)g.c[i][27]=(10-i)*(10-i);
for(int i=10;i<=18;i++)g.c[i][27]=(19-i)*20;
for(int i=19;i<=27;i++)g.c[i][27]=100;
g.c[18][28]=g.c[28][28]=1;
g.c[27][29]=g.c[29][29]=1;
//我这里求的是n-1的\sum，所以n要加1
for(++n;n;n>>=1,g=g*g)
if(n&1)f=f*g;
printf("%lld\n",1ll*(1ll*f.c[1][28]*f.c[1][28]-f.c[1][29]+mod)%mod*ksm(2,mod-2)%mod);
}
```