kmjp's blog

競技プログラミング参加記です

yukicoder : No.1085 桁和の桁和

このテクを思い出せてよかった。
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で出たんだっけ?