设为首页 加入收藏

TOP

Gym100025K
2019-04-05 22:08:16 】 浏览:52
Tags: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); }

 


编程开发网
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇libmxml数据结构(源码分析) 下一篇CPP strcat函数使用

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

array(4) { ["type"]=> int(8) ["message"]=> string(24) "Undefined variable: jobs" ["file"]=> string(32) "/mnt/wp/cppentry/do/bencandy.php" ["line"]=> int(217) }