230°

洛谷:P3281 [SCOI2013]数数 (优秀的解法)

刷了这么久的数位 dp ,照样被这题虐,还从早上虐到晚上,对自己无语...(机房里又是只有我一个人,寂寞。)

 

题目:洛谷P3281 [SCOI2013]数数 

 

题目描述

 

Fish 是一条生活在海里的鱼,有一天他很无聊,就开始数数玩。他数数玩的具体规则是:

  1. 确定数数的进制B

  2. 确定一个数数的区间[L, R]

  3. 对于[L, R] 间的每一个数,把该数视为一个字符串,列出该字符串的每一个(连续的)子串对应的B进制数的值。

  4. 对所有列出的数求和。现在Fish 数了一遍数,但是不确定自己的结果是否正确了。由于[L, R] 较大,他没有多余精力去验证是否正确,你能写一个程序来帮他验证吗?

输入输出格式

 

输入格式:

输入包含三行。

第一行仅有一个数B,表示数数的进制。

第二行有N +1 个数,第一个数为N,表示数L 在B 进制下的长度为N,接下里的N个数从高位到低位的表示数L 的具体每一位。

第三行有M+ 1 个数,第一个数为M,表示数R 在B 进制下的长度为M,接下里的M个数从高位到低位的表示数R 的具体每一位。

 

输出格式:

输出仅一行,即按照Fish 数数规则的结果,结果用10 进制表示,由于该数可能很大,输出该数模上20130427的模数。

 

分析:

数位 dp ,有点强大,又是一道需要感性理解的题目。。。

 

首先我们准备好 dp 状态: dp[i][2]  ,表示共有 i 位的 B 进制数,前缀子串的和。

dp[i][0] 表示无限制(甚至允许前导 0 的存在),

dp[i][1] 表示当前最高位不超过 d[i] (d[i] 表示读入的 B 进制数从后往前数的第 i 位)

 

那么 我们考虑 dp[i][0] 的转移:

假设当前 dp[i-1][0] 已经得到,那么 处理 dp[i][0] 就相当于 在 dp[i-1][0] 的基础上,在最高位(即第 i-1 位之前)加上一位 B 进制数 x 。

那么对于前缀子串的和来说,x 的贡献也就是让 后面的 i-1 个数字多了 x 中选择(0 ~ x-1),而 x 本身对于前缀子串和的贡献就是 x * B0 + x * B1 +.....+ x*Bi-1 (看不懂可以多想几遍,注意抓住贡献这个关键)

那么 我们就可以列出转移式子了:$$ dp[i][0× dp[i1][0]+ \drac{B(B1)}{2} × B[i] × S[i1] (B[i] = B^{i} , S[i] = \sum_{1}^{i} B[i]) $$

而对于有限制的 dp[i][1] 我们也可以对应的得到式子: $$ dp[i][1= d[i× dp[i1][0]+\drac{d[i](d[i]1)}{2} × B[i-1] × S[i-1] + dp[i1][1+ d[i](sub[i1]+1) × S[i-1] ( d 的意义同上,sub[i] 表示读入的 B 进制数的长度为 i 的后缀子串对应值) $$

那么 对于 ans 的累加就是: $$ ans=\sum_{i=1}^{lenmax(0,pre[i+1]1× f[i][0]+f[i][1$$ 也就是说我们一步一步去处理 dp 数组,然后就可以同时累加答案了

为什么 ans 这样累加? 其实上面的式子就是在说,除去当前处理完的 i 位,剩下的(前缀子串对应值)有 pre[i+1] 种取法(因为可含前导零,所以方案数就是前缀子串对应数值)

但是前缀不能取到完全状态,于是 -1 。然后加上有限制的 dp[i][1] ,就是当前可累加的答案了 

emmmm...麻烦死了...其实不是很难理解,但是很难想到可以这么转移...之类的(都是借口

于是...就可以上代码了吧?

 

 

代码

 1 //by Judge
 2 #include<iostream>
 3 #include<cstring>
 4 #include<cstdio>
 5 #define ll long long
 6 #define int long long
 7 using namespace std;
 8 const int M=1e5+111;
 9 const ll mod=20130427;
10 //#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
11 char buf[1<<21],*p1=buf,*p2=buf;
12 inline int read(){
13     int x=0,f=1; char c=getchar();
14     for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
15     for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f;
16 }
17 ll B,len,ans,d[M],f[M]={1},sum[M]={1},pre[M],sub[M],dp[M][2];
18 inline void prep(){ //预处理
19         for(int i=1,j;i<=1e5;++i)
20                 f[i]=f[i-1]*B%mod,
21                 sum[i]=(sum[i-1]+f[i])%mod; }
22 inline ll solv(){
23     ll ans=pre[len+1]=0; //恶心的pre初始化,最后的坑
24     for(int i=1;i<=len;++i) sub[i]=(d[i]*f[i-1]%mod+sub[i-1])%mod;
25     for(int i=len;i>=1;--i) pre[i]=(pre[i+1]*B%mod+d[i])%mod;
26         //前缀值、后缀值的预处理
27     for(int i=1;i<=len;++i){ //dp 转移,查了半天发现没毛病
28         dp[i][0]=(dp[i-1][0]*B%mod+B*(B-1)/2%mod*f[i-1]%mod*sum[i-1]%mod)%mod;
29         dp[i][1]=(dp[i-1][0]*d[i]%mod+d[i]*(d[i]-1)/2%mod*f[i-1]%mod*sum[i-1]%mod)%mod;
30         dp[i][1]=(dp[i][1]+dp[i-1][1]+d[i]*(sub[i-1]+1)%mod*sum[i-1]%mod)%mod;
31         ans=(ans+max(0ll,pre[i+1]-1)*dp[i][0]%mod+dp[i][1])%mod;
32     } return ans;
33 }
34 signed main(){
35     B=read(),len=read(),prep();
36     for(int i=len;i;--i) d[i]=read();
37     for(int i=1;i<=len;++i) //繁杂的数字处理,坑
38         if(d[i]){ --d[i]; break; }
39         else d[i]=B-1;
40     if(!d[len]) --len;
41     ans=-solv(), len=read();
42     for(int i=len;i;--i) d[i]=read();
43     ans+=solv(),printf("%lld\n",(ans%mod+mod)%mod); return 0;
44 }

 

原文链接:https://www.cnblogs.com/Judge/p/9567620.html

全部评论: 0

    我有话说: