Educational Codeforces Round 84 E. Count The Blocks
传送门: 1327- E. Count The Blocks
题意：给你一个整数n，求10^n内（每个数有前导零）长度为1到n的块分别有多少个。块的含义是连续相同数字的长度。
题解：从n=1开始枚举，ans数组记录每个长度的块的个数。当前的ans[n]的值就是下一个n++后的ans[n]的值，这样每次只用算长度为1的块有多少个就好了。为了方便，将ans数组倒过来记录。长度为1的块实际上就是总数字个数减去长度为2~n所含有的数字个数。比如n=1时，长度为1的个数有10，当n=2时，长度为1的个数就是10^2*2-10*2=180，n=3时，长度为1的个数就是10^3*3-180*2-10*3=2610;
1 #include<bits/stdc++.h> 2 #define ll long long 3 using namespace std; 4 5 const ll mod=998244353; 6 ll ans[200100],p[200100]; 7 8 ll quick(ll a,ll b) 9 { 10 ll res=1; 11 a=a%mod; 12 while(b){ 13 if(b&1) res=(res*a)%mod; 14 a=(a*a)%mod; 15 b>>=1; 16 } 17 return res; 18 } 19 20 int main() 21 { 22 ios::sync_with_stdio(false); 23 cin.tie(0); 24 cout.tie(0); 25 ll n; 26 cin>>n; 27 ans[1]=10; 28 p[1]=10; 29 ll sum=p[1]+ans[1]; 30 for(ll i=2;i<=n;i++){ 31 ans[i]=quick(10,i)*i%mod-sum+mod; 32 ans[i]%=mod; 33 p[i]=p[i-1]+ans[i]; 34 p[i]%=mod; 35 sum+=p[i]+ans[i]; 36 sum%=mod; 37 } 38 for(int i=n;i>=1;i--) 39 cout<<ans[i]<<' '; 40 return 0; 41 }
投递牛客等公司10个岗位 >
