▼ 日記
パス破り解法 初雪   8/28 23:31 [586]
C++でのワイの実装がこれ
コメント欄で解説します

#include<bits/stdc++.h>
#define MOD 1000000007
#define rep(i、n) for(int (i)=0;(i)<(n);(i)++)

using namespace std;

int main(void){
string S;
cin >> S;
int L=S.length();
int dp[L+1][13]={};
if(S[0]==’?’) rep(i、10) dp[1][i]=1;
else dp[1][S[0]-’0’]=1;
for(int i=2;i<=L;i++){
if(S[i-1]==’?’) rep(j、13) rep(k、10) dp[i][(j*10+k)%13]=(dp[i][(j*10+k)%13]+dp[i-1][j])%MOD;
else rep(j、13) dp[i][(j*10+(S[i-1]-’0’))%13]=(dp[i][(j*10+(S[i-1]-’0’))%13]+dp[i-1][j])%MOD;
}
cout << dp[L][10] << endl;
}
シャチ   8/28 23:34 [894]
見ても理解不能なの草
初雪   8/28 23:37 [580]
dp[i][j]を上からi番目の位まで見たときの、13で割ったとき余りがjになる数の個数とします。例えば「7?4」という文字列が与えられたとき、dp[1][0〜12]はdo[1][7]のみ1で、残りは0です。
初雪   8/28 23:41 [664]
この時、上からi番目の位の数をkとすると、dp[i][(j*10+k)%13]=dp[i-1][j]という漸化式が成り立ちます。(a%b…aをbで割った余り)
初雪   8/28 23:43 [455]
?が出てきた場合、0〜9の10通りの数字になり得るということなので、kを0〜9の10通りに変化させ10回計算を行います。
初雪   8/28 23:45 [752]
文字列の長さをLとすると、このようにdp[i][j]を埋めていったときのdp[L][10]の値が答えとなります。プログラミングで答えを出す場合、計算するごとに1e9+7で割った余りを求めてオーバーフローを防ぐこと。
初雪   8/28 23:47 [415]
パス破りの問題文
「?6?42???8??2??06243????9??3???7258??5??7????543??6531??21?84」の、?をそれぞれ0〜9の10通りに変化させたとき、13で割って10余る数が何通りあるか、その答えを1e9+7で割った余りを求めよ。
初雪   8/29 0:1 [5]
修正
解説コメ1つ目do[1][7]→dp[1][7]
▼コメントを投稿する
※ご本人や日記と関係のない書き込みはお止め下さい。
他のプレイヤーの誹謗中傷、さらす行為などはお止め下さい。
マナー、ルールを守って、楽しく使ってください。



  



チビクエスト  このページへのリンクURL