Gym100025K

矩陣快速冪

設答案為f(i)

舉個例子：

當i==2時，包含0的值有：10，20，30，40，50，60，70，80，90，100；0的個數為11，f(2)=11;

i==3時;可以從i==2的情況遞推，

第一步：i==2時的數據範圍：1-100；在這100個數後面補0；補0後，這些數在1-1000的範圍之內，合法，0的個數增加了100個，也就是10^(i-1)；

第二步：把i==2時包含0的有效值拿出來，在這些值後面補0，1，2，3，4，5，6，7，8，9；

比如70；補數之後就成了:700,701,702,703,704,705,706,707,708,709;這樣70裡面0的個數就被計算了10次。至於700裡面由於後面補零增加的一個0，這個可以發現已經在第一步中計算過了。因此加上10*f(i-1);

但要知道100後面補數的話，1001，1003，1003，1004，1005，1006，1007，1008，1009都是不合法的。不合法的情況有9種，每種裡面包含0的個數為(i-1)。

因此遞推式為f(i)=10*f(i-1)+10^(i-1)-9*(i-1);

接下來就可以愉快的矩陣快速冪了。

#include<bits/stdc++.h>
using namespace std;
int f[10];
#define ll long long
ll mod;
ll res[4][4];
ll ans[4];
void Ans()
{
    ll tmp[4]={0};
    for(int i=0;i<4;++i)
    {
        for(int j=0;j<4;++j)
        {
            tmp[i]=(tmp[i]+res[i][j]*ans[j])%mod;;
        }
    }
    for(int i=0;i<4;++i)ans[i]=tmp[i];
}
void A()
{
    ll tmp[4][4]={0};
    for(int i=0;i<4;++i)
    {
        for(int j=0;j<4;++j)
        {
            for(int k=0;k<4;++k)tmp[i][j]=(tmp[i][j]+res[i][k]*res[k][j])%mod;
        }
    }
    for(int i=0;i<4;++i)for(int j=0;j<4;++j)res[i][j]=tmp[i][j];
}
void init(ll n)
{
    --n;
    res[0][0]=10%mod;res[0][1]=10%mod;res[0][2]=(-9%mod+mod)%mod;
    res[1][1]=10%mod;
    res[2][2]=res[2][3]=1;
    res[3][3]=1;
    for(int i=0;i<4;++i)ans[i]=1;
    while(n){
        if(n&1)Ans();
        n>>=1;A();
    }
    cout<<ans[0]<<endl;
}
int main()
{
    /*
    f[1]=1;
    for(int i=2;i<=6;++i){
        f[i]=10*f[i-1]+pow(10,i-1)-9*(i-1);
        cout<<f[i]<<endl;
    }
    */
    freopen("zeroes.in","r",stdin);
    freopen("zeroes.out","w",stdout);
    ll k;
    cin>>k>>mod;
    if(mod==1)cout<<0<<endl;
    else init(k);
}