このテクを思い出せてよかった。
https://yukicoder.me/problems/no/1085
問題
非負整数xに対するF(x)を以下のように定義する。
- xが1桁ならF(x)=x
- xが2桁以上なら、桁の和をyとしF(x)=F(y)
整数Sが与えられる、ただし一部の桁は不定である。
F(S)がDとなるような不定桁の組み合わせは何通りか。
解法
F(x)の特性として、以下がある。
- F(x)が0になるのはx=0の時だけ
- それ以外はF(x) = (x mod 9)、ただしx mod 9 == 0のときは9
これを踏まえF(10x+y)を考える。
- x=y=0の時のみF(10x+y)=0
- それ以外の時、F(10x+y)=((10x+y) mod 9)=((x+y) mod 9)=((F(x)+y) mod 9)、ただし(F(x)+y) mod 9 == 0のときは9
これがわかると、先頭桁から1桁ずつ決めていけることになる。
dp(n,d) := Sの先頭n桁を決めたとき、その値xに対しF(x)=dとなる不定桁の組み合わせ
を埋めて行こう。
string T; int D; ll from[10],to[10]; const ll mo=1000000007; void solve() { int i,j,k,l,r,x,y; string s; int sum=0,num=0; cin>>T>>D; from[0]=1; FORR(c,T) { ZERO(to); FOR(i,10) if(c=='?' || c=='0'+i) { if(i==0) { FOR(j,10) (to[j]+=from[j])%=mo; } else { FOR(j,10) { x=i+j; if(x>9) x-=9; (to[x]+=from[j])%=mo; } } } swap(from,to); } cout<<from[D]<<endl; }
まとめ
AtCoderで出たんだっけ?