TopCoder IncreasingNumber 题解

TopCoder IncreasingNumber 题解

由于数字是递增的，一般有两个惯用套路来处理：

1. 设 d i = a i − a i − 1 d_i=a_i-a_{i-1} di​=ai​−ai−1​，然后在进一步操作（不过这题用不了这个）
2. 可以假设这些数是一段段右对齐的连续的1组成:
   000011
   000111
   001111
   111111
   =112344
   这样显然是递增的。这个东西非常的重要,因为如果你要计算模数的话 N u m % M O D = ( 1..1 ) % M O D + . . . + ( 011.11 ) % M O D Num%MOD=(1..1)%MOD+...+(011.11)%MOD Num%MOD=(1..1)%MOD+...+(011.11)%MOD,也就是上面那么多连续的1的模数累加起来。

讲完了这些这题就瞬间会做了一半，我们设 c n t i cnt_i cnti​表示长度 ≤ n leq n ≤n的连续的1模d余i的个数。由于n太大这东西不好直接算，但是我们手写几个数就会发现，这东西是有很明显的规律的:
首先开始是几个无序的数
之后随着1的个数的增加，会出现一段一段循环，往往这个循环节长度很小。
那么怎么找到这个循环节和前面无序数的长度呢？
我介绍两种方法:

1. 考虑从i开始了一段循环如果前面出现了i，则循环节的长度位 i − l a s i + 1 i-las_i+1 i−lasi​+1从 l a s i las_i lasi​开始，虽然这个东西是错的，但这题这样做就对了？？虽然我也不知道为什么，但这样的确可以过。这样最坏也就是 O ( d ) O(d) O(d)
2. 这是个正确的做法：用z算法/kmp，从一个位置出发如果当前后缀与前缀匹配则前缀构成了一段循环节，不过时间复杂度: O ( ? ? ) O(??) O(??)具体实现可以看看我的code

有了 c n t cnt cnt数组，一切就变得豁然开朗。接下来考虑dp:
d p i , j 表 示 放 了 i 层 ， 模 d = j 的 方 案 数 转 移 ： d p i , j = ∑ d p i − k , j − k ∗ m ∗ C c n t m + k − 1 k dp_{i,j}表示放了i层，模d=j的方案数\ 转移：dp_{i,j}=sum dp_{i-k,j-k*m}*C_{cnt_m+k-1}^k dpi,j​表示放了i层，模d=j的方案数转移：dpi,j​=∑dpi−k,j−k∗m​∗Ccntm​+k−1k​
Code:

/*
{AuThOr Gwj
*/
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define rb(a,b,c) for(LL a=b;a<=c;++a)
#define rl(a,b,c) for(LL a=b;a>=c;--a)
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(LL a=0;a<b;++a)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define POB pop_back
#define ff fflush(stdout)
#define fastio ios::sync_with_stdio(false)
#define R(a) cin>>a
#define R2(a,b) cin>>a>>b
using namespace std;
const LL INF=0x3f3f3f3f;
typedef pair<LL,LL> mp;
/*}
*/
const int MOD=1e9+7;
class IncreasingNumber{vector<LL> cycle;
LL z[1000200];
LL  cnt[500]={0};
void z_function(vector<LL>& S){LL len=S.size()-1;LL l,r;memset(z,0,sizeof(z));rb(i,2,len)if(S[i]!=S[i-1]) break;else z[2]++;l=2,r=z[2]+1;rb(i,3,len){if(i<=r){z[i]=z[i-(l)+1];z[i]=min(z[i],r-i+1);if(z[i]+i-1==r){LL ite=z[i]+1;rb(j,r+1,len){if(S[j]!=S[ite++]) break;z[i]++;}l=i,r=i+z[i]-1;}}else{LL ite=1;rb(j,i,len){if(S[j]!=S[ite++]) break;z[i]++;}l=i,r=i+z[i]-1;}}
}
LL ext_cnt[500]={0};
LL t=0;LL n,d;
LL calc_cycle(vector<LL>& cycle){//处理循环节 
//	cout<<"-------START-A-NEW-ONE------"<<endl;z_function(cycle);rb(i,2,700000){if(z[i]+i-1>=cycle.size()-1){return i-1;}}if(t<n){
//		cout<<cycle[1]<<endl;ext_cnt[cycle[1]]++;}t++; ase(cycle.begin()+1);return calc_cycle(cycle);
}
LL quick(LL A,LL B){if(B==0) return 1;LL tmp=quick(A,B>>1);tmp*=tmp;tmp%=MOD;if(B&1){tmp*=A;tmp%=MOD; }return tmp;
}
LL inv(LL x){return quick(x,MOD-2);
}
LL dp[10][500];
LL c_(LL A,LL B){LL res=1;rb(i,1,B){res*=(A-i+1)%MOD;res%=MOD;}rb(i,1,B){res*=inv(i);res%=MOD;}return res;
}
LL c(LL A,LL B){return c_(A+B-1,B);
}
public:LL countNumbers(long long n2, LL d2){n=n2;d=d2;
//			cout<<n%MOD<<endl;memset(dp,0,sizeof(dp));cycle.PB(0);cycle.PB(1%d);LL las=1,lastten=10%d;rb(i,2,1000000){cycle.PB(las=(las+lastten)%d);
//		cout<<las<<endl;lastten*=10;lastten%=d;}LL len=calc_cycle(cycle);t=min(t,(LL)n);if(n-t>len){n-=t;LL rest=(n)%len;rb(i,1,len)cnt[cycle[i]]++;rep(i,d)cnt[i]*=(n)/len%MOD,cnt[i]%=MOD;rb(i,1,rest){cnt[cycle[i]]++;cnt[cycle[i]]%=MOD;}n+=t;}else{rb(i,1,n-t)cnt[cycle[i]]++,cnt[cycle[i]]%=MOD;}rep(i,d)cnt[i]+=ext_cnt[i],cnt[i]%=MOD;LL must_be=1,ten=10;if(n<=1000000){rb(i,2,n){must_be+=ten;must_be%=d;ten*=10;ten%=d;}}else{n-=t;n%=len;if(n==0) n=len;must_be=cycle[n];}dp[0][0]=1;LL res=0;LL tmp=0; rep(i,d){
//		if(cnt[i])	cout<<i<<"-"<<cnt[i]<<endl;tmp+=cnt[i];tmp%=MOD;}cnt[must_be]--;cnt[must_be]+=MOD;cnt[must_be]%=MOD;rb(k,0,d-1){if(cnt[k])rl(i,7,0){rb(j,1,8-i){LL tmp=c(cnt[k],j);rb(div,0,d-1){dp[i+j][(div+j*k)%d]+=dp[i][div]*tmp%MOD;dp[i+j][(div+j*k)%d]%=MOD;}	}}}rb(i,0,8){rb(j,1,9-i)res+=dp[i][(d-(LL)j*must_be%d)%d],res%=MOD;}return res;}
}solver;
/*
1311237 364
1311237 364
//*/
//int main(){
//	LL n;
//	int d;
//	R2(n,d);
//	int ans&#untNumbers(n,d);
//	printf("%dn",ans);
//}