米田氏が企画した「競プロ典型90問」を解いていきます。
ここでは私の試行錯誤やら解説の理解やら気づきやらをメモしていこうと思います。
競プロ初心者なのでどうか温かい目で見守ってください。
なお、本記事中のPythonコードはブラウザ上で実行可能です。
よろしければ遊んでいってください。
問題
kyopro_educational_90/005.jpg at main · E869120/kyopro_educational_90
twitter
try(1st.)
- $c$で作れる$N$桁の数字の範囲から、$B$の倍数を探して、それが$c$で作れるか確かめればよくない?
という訳で実装したのが以下。
def main(N, B, K, c):
*c, = map(str, c)
xmin = int(min(c) * N)
xmax = int(max(c) * N)
d, m = divmod(xmin, B)
imin = d+1 if m else d
imax = xmax // B
cnt = 0
for i in range(imin, imax+1):
target = set(str(B*i))
while len(target):
if not target.pop() in c:
break
else:
cnt += 1
return cnt % (10**9 + 7)
テストデータ・テスト関数定義↓
# 縮小表示
test_data = [
{
"in":[3, 7, 3, [1, 4, 9]],
"out": 3
},{
"in":[5, 2, 3, [1, 4, 9]],
"out": 81
},{
"in":[10000, 27, 7, [1, 3, 4, 6, 7, 8, 9]],
"out": 989112238
},{
"in":[1000000000000000000, 29, 6, [1, 2, 4, 5, 7, 9]],
"out": 853993813
},{
"in":[1000000000000000000, 957, 7, [1, 2, 3, 5, 6, 7, 9]],
"out": 205384995
},
]
def test_all(f, n=float("inf")):
for i, data in enumerate(test_data):
if i >= n: break
exp = data["out"]
ans = f(*data["in"])
result = "AC" if exp == ans else "WA"
print(f"{i+1} {result}: expected: {exp}, output: {ans}")
# 3つ目以降のケースでは終わらない
test_all(main, 2)
あかんわ。
確実に駄目だろうけど提出してみます。
結果(1st.)
やっぱりあかん…
提出 #32501844 - 競プロ典型 90 問
![](data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAATwAAACUCAYAAAAOPZUxAAAAAXNSR0IArs4c6QAAAARnQU1BAACxjwv8YQUAAAAJcEhZcwAAFiUAABYlAUlSJPAAACDjSURBVHhe7Z0JjBVVuscP2CCNggsiAgoqzJNFQdHRiI6TEZ/DmBYNSnwxEgngEhc0zpAQcd+GGWdxg5mnQjQah4nLgBrlDShvBtEYEUVZ9A0iorIpoiA0QtP97u90fXdOF1X31r23qvveW98vqVTVqfWr75z/WarqnHZNGYyiKEoKaO/NFUVRqh4VPEVRUoMKnqIoqUEFT1GU1KCCpyhKalDBUxQlNaRG8F588UVz/vnnm08//dQLaYZ1wm+55Raza9cuL1RRlGpkH8ELEwZg28MPP2znTG3Bt99+a8aNG2fvww/bbrjhBrN06VIrYKxL+AsvvGDOPfdcc8wxx9iwfMh1TjnllLwT+8m1FEUpX/YRvB//+MfmzjvvNGPGjNknIZ911llm9erV5sgjjzSvvfZaoCi2Bg888IDZtGmTFRtXeA8++GAzYsQIs3jxYnPqqaeap556yorfOeecY7ePHTvWCiViKGKGnRs2bDDz5s0zZ555pg1zxXTkyJHmjTfeMEuWLDG33XabDXv00Uft+oIFC8zxxx9vwxRFKX9y/mmBWFx55ZXm8ssvN9dff70XGozsixgMGzbMC00WqqD33HOPWbZsmXnooYcCS28rV640v/3tb+0ygj1jxgwzefJk8/Of/9wKJKI9adIkM3ToUCuEnTp1svsi9DfeeKNZvny5Xc8FoocIcz5FUcqXbAkP8SDBu21ZCBelG0pTQVVIl0MOOcT07NnTfPHFF1b8pLrnTu65XSilsZ3jBGlbc68r55X9ECcEjxIpohVU4hw0aJC5/fbbzZYtW6zYUUq75JJLIouTlvAUpXpoUaWdMGGCFSyqdiJOIipuCU+EB6ESYZKq4V133WVLeogDosBECRFGjx6dLUEhZNJWSNsawkIpTarQW7dutefr27evXQcElfNyflf4EOaXXnopW8IT8fZXyeU+CGc75wiq0rrCqyhKFUGV1k99fX3T1KlTm04++eSmd9991wttJiNETRnhsNvZzyUjWHYb+whz586152Gby5o1a5rq6uqy5+E67Mf+IMf5ry/I/kH34R4ry/4p7LyC2Bl0rH/y26woSnkSKHiCiJIrDggXYWzzg7i420RsgkQJXGESkUU8MiWu7HI+IeF+3PPLPfsFVgRSbGG7CJY7hdkG7v0qilJ55BQ8P5LgmQchosJ2EbAwsQMRJ/8+7nkKQUplrlC6Asg5mbN95syZ+4gX20TwwgQxbGJ/RVHKm8gfHtPmRvscbWijRo3yQlsiLy4+++yzbNsfk7Tb+aHNjbY3dx/a3DLiYV8G8FY1KrQF8tkJuG9MM8Jn5927d8/OM3abzZs32/UwaLOUNkh5WeGCnc8++2x2n3xvsRVFaXvyCp68oPj73/9uE3iY2AEiwOcdvNUNehubDxEt3qjyZjXKm1R5QcHLB15+PPHEEy2O4yVMt27dzGGHHWbXmbdr186sX7/erudDhD5TKswK34MPPmjt5Jr6gkNRKodAwRMRQejkjav7FjQMSmk9evSwIlOI4LlvehEShDXftUSIebPK9fhEJKiURWkzU+U0hx56qF1njijKx8jyxpfpySeftGEg90QYn6G4566trbWlUkSQ4/N9sqMoSpnQXLNtRtrOmHK1veWikIZ9aV+L2gYm7YJyj1GuIYhtckzQfUob3qJFi+zc34YYdIzck7T9KYpSvuT800JRFKWaiPzSQlEUpdJRwVMUJTWo4CmKkhpU8BRFSQ0qeIqipAYVPEVRUoMKnqIoqUEFT1GU1JD98Li+vt589913ZufOnXaDoihKOdOxY0dTU1NjDjroIPu7ZxSs4KF5/I9KTyLt26ev0IftDExUjVSzbblIo91ptLmxsdF89dVX1m46BclHVt327NmTSrFTFKVyQbPQrqiowimKkhpU8BRFSQ0qeIqipAYVPEVRUoMKnqIoqUEFT1GU1FCS4L388svmiiuuaDG6f6lwLs45Y8YMLyQ37Dd69Gizdu1aL6Q6wJ6JEyeWpV2MV3LHHXdE9lE+4j5fUrz33nuxxrW4z5cESfgmCd2ISkWX8HDC008/bTZu3GguvfRSM3z4cDvxQJOE88u12spxScDzFLuI5IUMxCSQeH/5y18mkgkWe0+5kHOL3cXGHZ5dnPEOMZR7SiKOxRGH4/a1iKvcVxIZYCyCxwhf5FRyo0z+nEsilhspMKgYozgv52eksmeeeca8+eab5pVXXjGDBw+2QzXKiGRJQEScNWtW9ronnXSSeeONN7ytlQt+wTae4+uvv27DVq1aZeeFwDjA27Zt89ZKB1+PHz/erFixwguJDxIYYxjjQ3yJTxcuXFhwAuY8+cY5LgRsvvvuu8306dOtL3r37m3vLS7iisNx+5p7Amzm3kjf3GucFCx4rgrfd999NiLOnTs3+/CYH3HEEWbIkCF2TkJC6OCCCy6w+xKhJJL06dPHbvNDyY1r+HN1HgClOUp1TAy5yHaJEDfeeGPowN9x8OWXX9pxbmXs22uuucbU1dVlBV0En/uUsJtuusmGsYwz3X2YCJdnGlbFcUtfcZYkhHXr1tmExbNj4n4GDhxo53I9uVf+uQb8JzZzf2y/9tprbZw477zzsvbJfbMvz8R9Vu75BLH17bfftv5F8G6++WZva3wQb/CnxMGjjz7a/P73v7cZuNyrxHf3mT/33HP2/vDVxx9/bKZNm2bHbSY9sC/2iD+Z5Fjm/jBBMnGO479Q4jNChC8OP/xw+6zddFAKQXGYQkJr+Jp1FzmGwfdJ19yDpF+GVGVw/zgpWPAkMSBul112mS1VicjgECIojBs3zoYxbiwQidxlxOqDDz6wiSwIzs01EMmzzz47+7AkNxZx5Rxs58Hdf//9kQbvLoXjjz/eDhSOk11xojTE9bkvcmaE/YcffrDbuD/Jqf/5z3/aZRIw++zevdtGGuwknIyCUpYLkZAIx3a2UQoJEsVSOP30022idZ91Pkg42Iy95MZETuwiTnCfCCalAPGXlCQkMRPG8a7gYSu+5PjTTjvNxjUylCQgrnAfCJUk5HwQbwcMGJD11WuvvWbjPzZjO/e7YcMGG/8ljuKvDz/80MyZM8euE96/f3/re+AZ3XvvvVbYOZ6xnSXR4weeB+MmS1iphMXhXCTha3RASrKTJk3Kpl38gPghqGRCcRJrGx5FUhINjpMblUhF4sZhsvzOO+/YXCbfgNvysMiFJCcJQnIayWH8OWhcYNcLL7xgnS1th9wTgoFzuTaOIoKI4EnJiZyaiWXC2IdIT6ThORBOxEbc5FjmS5YsyYoRNr711ls2csWJPGcyGp4lPmQQ81xwDP7l3vHl8uXLvS3NYM+wYcOyOTyldkqSlKhYltxcSliEIT74OumMS+BaJFh8IPckQhQEtRYEQ3yF7/3VOgSRZ4HNxA8SNvBzu8QX9qG3D+IQ8YX44G+KoQBBlTtoWykExeFly5Z5W4OJy9d9+/a1+xPHsBu7OLcLPiEtIYZh6b1YYhM8yYl4iP4cmURKTw48XIwhRyQBU6qJGrElQTKXagaOIpclt2Ubk0TepMFGrkubIcIlxXyuT45VCiKELjxXsVGeQxKIABCpo5TyXEiYLhw/efLkrO8QU+DZsY74I+KS2NjOxLMs9NqlQBx87LHHrN+Cnn0usHn//ff31pohs5U2MiaqZl26dLHXkIQswoqA3nPPPbamQslJII5TVYYpU6ZYsYgbNw6vX7/eC41Gsb4WASONYjdiGCRq0iyGP+IkNsGTSOMXOyBHefzxx+281FyL4jdCRwQZNGiQF9p6EJml6oMtOEScj7N5DpTACoHqBRGG81Ga4zwkECAxUZKQtk8gkrJvnGCTlIq5Dl2GSWZETg1hkY8SDDaEtbdQ+uWcErE/+ugj60dKkf7Ehm+hNV4EcU+8ZZQqnfiSkpfrkyC7xVckZL/ggbRhUxL65ptvbEkdv5EGbr31VntOEdZjjz3WPgvxMedG7NgniTbpoDjcq1cvu560r93zUiJEGLF706ZNtnRIRsA9UTjK1eRVLCUJHsVViRhR4EGj8lBsriXFcXJK+sCSqh7FaCZKkxSXkwBHUC0hJ5ZrUUpFoHA0uRXh9CvYtWtX76hokNvJsyFyuJCJcA2pst9yyy1FvUENA/9xz9KWhehQ3TjuuOOsfWIXkde1a/Xq1TacfblnfOO2DyFa3Dfbyf1pw21oaDCzZ8+21xB7ZQ6ILKVM7oX4QmKhnYl1fM1xIlClQnsSGQvnxA4SHgIzdOhQK1iEc9/+RCe+IvGyD/eMndwjiZZqm7Qt8yyoBq5Zs8b6TZ4XNh544IHeGY3N/LkO13vxxRetrW4zTdR21XyExWHaS1vD1/5CDtt4jn/605/sc2WZfQnnOpwzTrIdgKLchXYeKDkRzvFDkZVGSiIDEZQ3lVSTJCwMnCpFYyJFGHJtcMVTjsd5QaXNINqy40RyQnLbfM+lWLQD0PSQZl+TqUTpALQkwasWVPCqDxW89FCI4MX6llYpHEqytH0mIXaKorREBU9RlNSggqcoSmpQwVMUJTWo4CmKkhpU8BRFSQ0qeIqipAYVPEVRUkOLD48VRVEqkaL+tOAn5jTCf47Vans125aLNNqdZl/rnxaKoig+VPAURUkNKniKoqQGFTxFUVKDCp6iKKlBBU9RlNSQqODR+zDD1dFldWvRFtdUFKUyiCx4fKd3/vnn29GYEBQGlnEntpXy8TJdttPn/9KlS+06guW/xuWXX26vI+ulXrMtwb40iDIZEH5lnibS4l+XSvB1JMHDgDvvvNMObsKAHXDbbbfZUZuYHn30URsWxl133dVCuB5++GFvy79ZuXKlnctIZKNGjbIDgyByjG3BNZ588knz0ksvxXbNJOBZSYbAPMj5iDtjvp511lleSLTjygnJoLjfXBkPH4Weeuqp+/ToTMZWiRkW950vTuXzL5Nk7JWCWwAJE/IgX7vHEV94Nm0Kv1k0NjY2ffLJJ/aXiyAeeughO8HWrVubMiLUdPLJJ7eY6urqmjIG230E2Xfu3LleSDic393v3Xff3eca/u2lXlPIZXsh1NfXN/3617/O3hNz1gl3IXz+/PneWvTjiiEu2/zgL3wAPPOpU6fauZ/Zs2fvE45vJk2aZI8Rm+MmCbv9fsGOoHjm9y9EfV6lkJSvuW9J/+Da4uL3ddTnVSrYjYZFIVIJ7/rrr7cTOdoNN9xgh2YLK+G5OSBDsjEup7+05c/dyP0Yl9LNEeHiiy82v/rVr+y1mIdRzDWTYMOGDXbes2fPFnMJFxYuXGj69evnrUU/rlwQf8lvTOToPXr0sDm8C6W3HTt2tMjxOTaTAMxvfvObFsMUVgIffvihrYHICHknnHCCrZn4Sy1+/7J97NixdhxWgeeVxODaSbB48WJzxhlneGvGLhPmEuRrxq71j6vb1oMMRW7DQzBkOEYSoisoV155pQ2TgZwBERRBDBJGFxIKEcBf7WHs1Z07d9rl3/3ud3ZZqlFc008h10yCTO5mDjjggKyDmbNOuECCJ2KIqEGU48oJ7guxciMyY7EyepQLAnHiiSd6a83g40suucRbqyyoproJlgT9/ffftxC8IP/ynLCb/Yi/iAAC6D6/coV7xh534G2WCXPtDvM1NkqBBFzRbwsiCR7qffvtt9txZR988MEWgkI728iRI21bG6XAQuGhMbC2m4MIRx11lB2Ql/Y8SnmClC5pz+On4UoCccfWSojspYBfyaCkTTYt5PIvYQw2/cADD9gMHHGsBvL5GpEjvUJbv8iJJHiU3KR6haOkZMfECOPz5s2zLxRcYyiBufsxBZXKOO/27dsDe3ngvJyfYylR5iPqNZPCn/Mxd3NH1qkK+G3Nd1y5wX35Szb+0g9Vvc6dO1eVsPtLsf6Sbph//bA/x5VrCd6Fe/XXNlh2ayRRfU38IJ60JZHb8KSENXr0aFtcl1KWW8KjJCZqHjRxDMe6CZmi8IgRI/apzgLn5fxyrB/aFJkKvWZSSDVGMgeZu+FEFL+t+Y4rN7h/t83O36YH77//vm3jqib8bXb+Nr0w//J8aPuWN9IcT4ZRrhmaH3+bnb9NL8zXFIDcN9lkFmQabUnkNjyBSH3FFVfYwaODPimgvs7nBgsWLLAiSASh3QLDeSlBtXjmzJnW6Rz//PPPhyaMqCW8Qq6ZJET8q6++2n7Cwz0zZ10SBCVlfzsH5DuuHCEO0BTB/dIeNWHChGxCx6+bN28OFWz8gl+fe+45M2bMmBaJopyh+eTcc8/NxklKK2TyQph/eS60202aNCnweZU7FCgQKu6diWVpi8vla3k2cpz/ebUJvKrN91kK8DqZzz0yxVk7sfyXv/zFfhoin4xkcny7zmtrXkXz6l1eYbMPc/aT5VywneP9r7Q5n3ymwpSJZCVfM6nX+eVANduWizTanWZfR/0spZ03t0qdr+2hWqFqVq22V7NtuUij3Wn2tfZ4rCiK4kMFT1GU1KCCpyhKalDBUxQlNajgKYqSGlTwFEVJDSp4iqKkBhU8RVFSQ4sPjxVFUSqRqB8etxC8tu6cr63gp+Zqtb2abctFGu1Os6/1TwtFURQfKniKoqQGFTxFUVKDCp6iKKlBBU9RlNSggqcoSmpQwVMUJTW0ynd4M2bMsPNrrrnGzoH+/+fOnWvuv/9+27c/401MmzYtO/ZtEIwnMGXKlNjHeojy/dKiDYvMs588a3bs2eGFFMcBHQ4wY/qNMT/p+RMvJFmifptVqfaFUc0+DSPNvi6L7/AYrYnBXhjk46STTjLDhw/PTvfdd59ZsWKFOe+88+xIaDJ822WXXWbefPNNM336dHPEEUeYZ555xq4T3pbEEUGAc3CuYiFjuOOOO7LP8b333vO2lEa52CdglxtfmIhLcY7lWm42+30rE4WDOEmjr4VES3jc8Pz5880f//hHu37zzTeburo6u1xpJbwJCyd4S/Ew82czvaXCkMjPc+T5MqgzI2KFjYAVNdcvF/vCcO2OQiX5NIwo/nVJs6/LooSHkxg+EaG66qqrzMKFC+1A3ii4W8JDzb/77jt7TLmW8FoDyeGlCYCcj9Lv2rVr7Trb+/fvn40ICD8DOieREyYNkVpycSaWJaL7YTtjDDM8YiXjt9N9BkEwJjPDG0YRu3KmnHydaAmPhHrTTTeZjRs3eiEtS3kulVrCG3ToIHP1CVeb9TvWm2lLptmwi/pfZOqOqTM17Wvs+j+++Id5fMXjdlnIlSsidNdee21ee3m+jO163XXXhe5Taq4/5ZQpptcBvcyfP/yzWfnNShs27YxppveBve3y1l1bW2wTouT6RO7JkyebLVu2mD/84Q/m6KOP9ra0hMSxbt26Fm3A+SjFp2f0OsOMGzjOvL3x7azfSvWpC/aQ4ZOJh9nEs7n77rvtIPhhz8VPmn1dFiU8jGKwZkSOxPv666+b3r1771Nfp1QDzCnNBZXwmNget9iVyvCew01tTa3p06WPTShMI44aYV7+9GUz9n/G2unLHV96e0eDEemxndw9zF4iEANYX3zxxYk9E2zBLuzDTiBRgNj213/91a4XA/dNfBgyZIi1NwjspGZATaC1+Emv5kb4gd0G2gwtDp+6YDOcfvrpdh4Epbt+/fpFFrtSSYuvExU8qaIhdNu3b7cluNWrV5vBgwebV155xYoYYgjLli1rIYKUcCgZXnrppS3C42qkj4v+B/c3n3//uWlobDADDxlop227t5nnVz/v7WHMq2tf9ZbyI6U2hB6Civ7F5P7FgC3YhX3YSeLv3rm7eWfTO94exixev3ifHD8KxI1HHnnEjBs3zk4sE+antRM+NlLKWbV1landr9YMPLR0n7oQf9966y0b95kHxee2EPm0+DpxwUPoevXqZbp06WLbm7766itva0uGDh1qIwFCiCC6SOmQ7bztLRfIFbt27GpWbFlhq7RElMNqD/O2Fg7PC/snTpxoc0Sq/p07d8624UFriR1gD3ZhH3aedsRpVgTiYMGCBWbEiBHWBiZKqvjXpU0SfkbgqLZSnUXkfnTwj0ryqQv2IHLjx4+361TbKAAQ7tLaIg9p8XXin6X07NnT9O3b167T1kQxXl5WUGKjLUOgsZ7wCy64IFulnTVrlt1GSc9N+OUAuWKXjl3Mhf0uNIO7DTY9OvewiYUIgxgWCiJHInAbqc8+++xsxOd50g5ConFLvkmUern/bp26WbuwDzuxT0SgVBBzN/PCRmx1oZTb2gkf27CVdlnarvod1M/s2ruraJ+64Ff86zZBjBkzpoW/ieNz5sxpVZFPk69b5cNjqmW8eaEBftWqVVbY5HMU2datWzfboCmN9CRiSjLSwElE4AXIOeecU1CDZhSKaeAmkvgbtmnghdXfrjY/PfKndhnINeWFhhD3q/wwim3IFlumLG5ux5k4eKLN9ed/Pt+c2fNMc0inQ2z4roZd5olVT9jqjktr2RdGMT7lxcTIviPNvM/m2eqr+0Lq6/qvy8anYaTZ19rjcQEUkzhKpdwFr1QqUfBKpVIFr1QqSfASrdJWE/xGExdxnisuqt2+INJoM6TVblDBiwj/DMbhXM7BucqNarcviDTaDGm1G7RKmyFqVaASqWbbcpFGu9Psa63SKoqi+NASXoZ8OWPDutdMw0dPm6bd33shpdOu44GmZsBlpqbPCC8kGarZtlyk0e40+1pLeDESdyQBzsd5i4VPe/iLJeiL9UIoR9v4JMntNAEIk+8Oq9Vuv0+Zsx7X95blaDM+xteubXH72kUFLwJxRxKhmPNKIti5c6f9c6VUysk24LvMp59+2v5zKfDBNV2Jye+I/GPM1/ulUAk+xUZslT+QeAb+vzIKodx8jbDde++9ifvaRQWvjJCIH9Y9FPDhNn+i8HtOpYGY5eomiLD6+nqbCNyET9dhbp9w/IROjxqVgN9O9xkIQT4lLlRyV2D5fI19/FZHBxiHH364F5q8r7UNL0O+to/6l1u+eu/Q52em9sSrTLuaf/9r2Lhjk2nXodbUfzDL7Fm3cJ99Grd9brYvuM4uu9TW7dtjLEKXr3soRDBf11BQqG013YeY2lNuNO1ru3khzfdu57u+MTveuM0udznnEdO+61F2uamh3tS//9/Wbpcg24j8+boJIjHwgzkCELSdDIFfFHP9V12o3bXDrjMdj/5Pby1DY4PZ+83H1kbxaadBl5r9/+OiTDGhuYuohs3Lss/DJchuEnu+LqFy+TSKvyvR15DLn1F9rW14CYKzt734X2b32vmmsX6L2bHoVrPn8//1tjo07jE/fPRX890LFwSKXRhRuodKioavPjDbXx1v77tp9zazc8kDofdOgsc2noU/AYSBPfm6CcqFlBJyJYBiqF/6iLWFBG/tmnORafh6ubf13zQ17LTPhH2DxC6MKF1ChYFwJNEVWBp9rYJXZkhOnqt7qEpFSm75ugkKg2dRaOeQ5QAl9nxdQoWB2LVW7zhxUq6+VsFLkvYdzP4DLjEHXfi8rQ7lgwiRr3uocqLm8KHmoNFzzQFn3uWF5CZKN0FhlIvYtavpbDpnqoFdR822zRb5QLCidAkVRDmJXbX4WgUvSaRKm6ke7VrZXGLLBSKHk93ugtzuoYBEQAMw3UPRmzTbCykxxIlUc6JW7aJ0E0SbDWHYho2skwBo/+LtbVKfK0RFqrRRq3b4Ep+6VVF/l1BBPl20aFGrdQUWhSR8jV+xCb/SZo1P//a3vyXqa31pkaHQxl6Bhu6aHsNMfSYB1HQ/vmWD9tfLzX4H9yvqpUWcFGsbJdKOx/4i22DvNlzTbmma9pr2nZvfrhXSkN1aFGs3dkqDvf8lxd5v15j9uvb5t48zIhAkAG1ld5p9rd1DFUCxESUOylXw4qASBS8OKk3w4qBSBE+rtBHg95kkSOq8hVDNtuUijXan1dcuKngR4F/BuJ3K+ThvW1PNtuUijXan1dcuWqXNkK8qUMlUs225SKPdafa1VmkVRVF8aAkvQ9ScMY7udaQK0Frd6WgJLzeV6NMw0mgzaAkvIeLoXofjS+lOh++R+C6prb/LqhbKwacC3xwGfXMWFl4s5WIzcTfoW7uw8DhQwSuAUiOJUMp54u4yKO2Ug08lE/N3DxUWXirlYDNxNqgbqLDwuFDBKyMkgpOjAzmd2z0U2yu5y6A0In9R8FcBMJduk4SwLr+quSuwsG6gku4eSgWvBOhep8svZtl/DOU/Q/6v5D9LCeOr9aggYAgePWpQnCenoxMB+bWM7QMGDLDLsHHjRjsvpicKJRi///ibphSfknAfe+wxu4xPSbysu7+W8QtWUI8gYeFJQNzN2peJ08RtNyzq/+ACmTKD7fN7HP8RT506NZtRQ9++fVs8A36hI96HhceFCl6peP/L8n/lfgcfYzr2zjinyG6hhCjdQ5FrJtFlkJKpqu1p/l8WH3bodZqp6TawZJ+W0j1UayH/y5qM/fsf11yq5JdIwqL+D+5CvIzSPZSU/PziHhZeCip4MdK0d49p3FVa9TJK91CIXSV2GVSJIH6ltnnRNEFJhTYp5pXwoqlx52ZvqThofonSPRTxO6hnlLDwUlHBKxWvC6jOmarPns8WmIYtq7JhhVYDiBD5uodSsUuedh2au4Dq2H+U2bVqttm7/fOifYq/ELliuodqbaQLKDpPqF/aXG2nEwFbzS2gGg9RuodqbbED/Q4vQ9Tvl/w/X9susodda/Z8/o9M1We4jSi71y00tUPGm91rXs1ZBSjmZ2sSCW0iK1as8EKamT59emixX7/Dy43fp7TXdRo81uz+1xzT8UcXmoZNS03D1ysS8ykE+RWf8m1ZUHipvg7qRED6uaNkJz0AUa1t3+nQnFX4Ym1G1OgGyoUhDYYOHWrb/lxyDXUAhXyHp4KXIQ7B2/v9BjuGhdlTn0k1tW3eLZSggpebMMHbteIps9+BPW33UHu/X2/ad+5eNj4NIw7Bo7srSnPtOh+WEb+vzX5eN1GM8fHD/z2/j+C3tc2gglcgpUSUYlHBS5Zq9mkYabQZChE8bcMrgLh6mojrPErppNGnaY7HKngFEEf3OhxfSd3pVDtp9Gma47FWaTNUc7VPq7TpIc2+1iqtoiiKDxU8RVFSgwqeoiipISt47dur9imKUllEabdzyapcTU2NaWxs9NYURVHKG8Ru7969pkOHDl5IfrJvabdv325/cWloaPA2KYqilDcU1OhOqkuXLtH/tGCB2e7du63geUGKoihlCwKH4HXs2DFy1TYreKBCpyhKpVFIO14LwVMURalm9NWsoigpwZj/B36D9c0eeIamAAAAAElFTkSuQmCC)
解説①
手も足も出ないので大人しく解説・想定コードを確認します。
今回は3段階の解説になっているので、一つずつ見ていきましょう。
kyopro_educational_90/005-01.jpg at main · E869120/kyopro_educational_90
想定コード
kyopro_educational_90/005-01.cpp at main · E869120/kyopro_educational_90
Pythonで書き直したのが以下です。
def kaisetsu1(N, B, K, c):
mod = 1_000_000_007
dp = [[0]*33 for _ in range(10009)]
dp[0][0] = 1
for i in range(N):
for j in range(B):
for k in c:
nex = (10 * j + k) % B
dp[i+1][nex] += dp[i][j]
dp[i+1][nex] %= mod
return dp[N][0]
# 4以降は終わらない
test_all(kaisetsu1, 3)
結果
Subtask1が AC になった!
提出 #32502123 - 競プロ典型 90 問
![](data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAScAAACECAYAAADSpe21AAAAAXNSR0IArs4c6QAAAARnQU1BAACxjwv8YQUAAAAJcEhZcwAAFiUAABYlAUlSJPAAAB+lSURBVHhe7Z0LkBXF1cebp7yRhzwVUPCTh4KCaImGlEKUmBVSKqVlQUmJUSuIUhqqKFFUjMbElEGCKV8QDJSPQihBy/BF0foiYIwKIk8VFDE8FZTnIqy73/5659z0DjP33rl37u7s7vlVTd07Pc/Tffrfp/vOna5XVo5RFEVJGPW9T0VRlESh4qQoSiJRcVIUJZGoOCmKkkhqvTgtWbLEXHXVVebLL7/0UipgnfR7773XHD161EtVFCUppMQprBID2/785z/bT5bq4Pvvvzfjxo2z9+GHbXfeeadZtWqVFRvWJX3RokXm8ssvN6effrpNy4Rc5/zzz8+4sJ9cS1GUeEmJ0+DBg82DDz5oRo8efUKlGzp0qNm8ebM59dRTzbJlywIFrCqYMWOG2b17txUGVyRPPvlkM2zYMLNixQpzwQUXmHnz5lmhGj58uN0+duxYK2oIlwgPdu7cudMsXbrUXHLJJTbNFb4RI0aY5cuXmw8//NBMmzbNpj3zzDN2/a233jJnn322TVMUpTAEPudExb7lllvMjTfeaCZOnOilBiP7UnEHDhzopRYWumG//e1vzZo1a8zMmTMDo6INGzaYP/zhD/Y74vqXv/zFTJ482VxxxRVWzBDYO+64wwwYMMCKVpMmTey+iPKkSZPMunXr7Ho6ECgEk/MpihIv9anoVE537AWRIWogSgnqRrm0adPGdO7c2fznP/+xQiVdHndxz+1C9MN2jhNkLMi9rpxX9kNIECciPQQmKJLr27evuf/++83evXutMBH9XHfddVkLiUZOilK92G7d+PHjrbjQvREhEQFwIycRCURFRES6R9OnT7cRFBWZCsxC5AVXX311KjJBdGRsi7EgRIDoR7qR3333nT1f9+7d7TogfpyX87sihYi+9tprqchJhNbfLZX7IJ3tnCOoW+eKpKIo1QzdOqG4uLhs6tSpZYMGDSr76KOPvNQKykWjrLyS2+3s51IuLnYb+wiLFy+252GbyxdffFFWVFSUOg/XYT/2BznOf31B9g+6D/dY+e5fws4riJ1Bx/oXv82KosRHJXESREDciozIkMY2PwiBu02EIUhAwBUREUQqenkkk/qeqdJzP+755Z79YihiJrawXcTFXcJsA/d+FUWpGgLFyY9UTj6DEAFgu4hNmDCBCIl/H/c8UZBoxxU1V6w4J59snz179glCwzYRpzDxClvYX1GU+Mn4ECZjRIwnMeYzcuRIL7UyMij+1VdfpcaqWGScyQ9jRIwVufswRlRe0e1AM7+uZQtjVzwqAO4vZ+UiZT9POeWU1Ge5vWbPnj12PQzG2GTMTAbCXbBzwYIFqX0y/ZqpKEpuhIqTDH7/4x//sJUxTJiACstP8vy6F/SrXCZEYPhljV/YsvlFTQa/GdhmYH3u3LmVjmOAv127dqZ9+/Z2nc969eqZHTt22PVMiCiXR1spkXriiSesnVxTB88VpbBUEiep8IiS/PLm/hoWBtFPx44drSBEESf3Fz8qPSKY6VoimvzCxvX4WT8oeiGKK+92mbZt29p1PhEweTBTfvljef75520ayD2RxqMD7rmbNm1qoz0Ei+MzPWahKEoe0LeTsR6WdGNF6YgyaCzjQdmO2cg4ltxjNtcQxDY5Jug+Zczp3XfftZ/+Ma+gY+SeZKxKUZR4CXxCXFEUpbrJOCCuKIpSHag4KYqSSFScFEVJJCpOiqIkEhUnRVESiYqToiiJRMVJUZREouKkKEoiqXfkyJGy/fv3m/JPL0lRFKWwNG7c2P7Xlb+V8bewIOpt27atjH/s169f94Io/pvHpA21hdpmTxB1wUaoC3aWlpaab775xtqJUPmpf/z48TopTIqiVC/oDvoThqqSoiiJRMVJUZREouKkKEoiUXFSFCWRqDgpipJIVJwURUkkOYnT66+/bn71q19VmlU3XzgX52Tq8GxgP2YS3rp1q5dSs+Hd6w888IDN2ySwevXqWPM37vPFRdy+XIi6kS/iW9nWrUzEfb4wamTkRKbMnz/f7Nq1y9xwww1myJAhdilUxaZCUbHkOlS0mkhcdpD/cec154srb+VcLLkKhVTAuMpazif3FUf+UQ5yPs7NNaKCT9x9992xiakEGXHYmZc4MVOJ6+ws/tZRbta9STI1F9WVysWMKy+88IJZuXKleeONN0y/fv3s9FAys0qccP8PP/ywuemmm+z1nnzySbN48eKcHKE6icsO9s80919U8IVHHnnEW8sPxGTOnDkp/zjvvPPM8uXLva3Zg53bt2/31vKHe4K3337b5j3rbj2JCvUJW/F/zgkbN260n1FgfscDBw54a/lBnjF3JHkuPpaPnVmLExcW5ceR1q9fb51bnIDPTp06mf79+9tPMg9RglGjRtl9qSDi3N26dbPb/BARcQ1/S0BBECURLbEwzRPbuS5MmjQpdBLPfOCemU+va9eudp2Ml3tzWwjuT4T4rrvusml8x3GC9nFbvaDWhTTZnouQ+wmzA4fmfqRsSHPv55VXXrH3QKPw6aefmkcffdTOZYgPsC//y+TTb4t7/377pJHhuPfff9/my4svvmgbmXxBUJivUOYw/PWvf22KiorsPXA9bJQy4LoClYp7JX3btm1m8uTJ1scnTJhg81+OEZvkWLcc3fMB66QzWSy+y/XxUSahBZn4NRe4R8qS87Fw7j59+thPyW+uzz1TRkC9Exu4b7ZjH3ZeeeWVdl3umYV9sdu13T2fIHmwZs0aWw/Jc8Eti6hkLU6SAQjRmDFjrCOJIFDgiAWMGzfOpjGvHBBdud8Rlk8++SRVSfxwbq6BoF122WWpDBI1FiHkHGwnMx977LGcMyATIrgUIgUgBU+l5rrcj0QhP/zwg93GfSFK2PjPf/7Tfr/nnnsq7QMcK+lugWMTadIq4lSk5UOYHemgrHr37m3vgWOXLVtmy5yy577xh507d9oyl3J55513zNq1a82rr76aarh69epljh07Zs9JhZQIjuMvvPBC8+yzz5rWrVvb7fnCjNGIMJXNH8WHQeXE38hvwLemTp1q84yypbIFlbcIK8eR7oKvP/TQQ3bfO+64o5J/rlu3zlbaTHM0puOiiy6yjYRbRzKBcGMD90TvA5GkHClPbEDcKB9sYZGok3KU+sfxrq/iR5IHlCV2SiOH/eRjwcUpHYRuZBQO16NHD5vGDWEQhYhYyfcPPvggq4KRzMAxRNWDENWnwmVb6aIgokwB4axEDLQUOAdpXJMKT8GL8EiL1qFDB7vwnTR3H44HKhOzc7nO9d5776XswvnI23y7GGF2pIP9uD+OZfJRysDfBUC8qGzkA9EBlRL4IyfrHMM+/AsdsSOvyItCdMEB/1u0aJGtdFxP7iEdVE78UXyWaebdRgSCyrtZs2ZWCPF7RJBjQSIubJQ0gXsh7/HrXCstSP2gMed63AMTyaaDY7gmtlIHKTcXynngwIGpKIleDBEavRy+4z/sI70e0oJsEV+77777bC+i4N26MKhUZDjOQPjsQuXi39U4CQbQ6lLRaKWyLRgpBD5FkXE4WnJadLaxoNxxdAvCcJ2eSIbZfrGb69IS5cO+fftOaPkkgpTFn7e54rdDIppsQFROOukkb60CGgMZ42HhFRgtW7a00RDrtJ6UGddB7JgxmciElruQkF/4B2ORUYWdBsVvp3SD3PI+7bTTbF5SCfFJEXv8EDupvK4w8h3R4ni/aOUK9Yp7QmyyiZ5cKE8Xjqc76wofkJesky80lnTfgO0s2B10bRHBXLuveYsTIoMjBlUeKsJzzz1nPxEW+vW5tpqoLw6AY/ft29dLLTxc1/01g5aEQmrQoEGqJSLSiYpUGAnxySOBVprKKy0O54/qeH7C7CCiofUnnTIKqsikE00EVVqQcUZsQWiJOhAGbKLick4RwTPOOMO28kTR+doUBGIpIiH2SCXkO2lcF5v9kI6AhI2H+subKJLvpIvYy7/siUCouNjJNUWY2C8OYcJG6SVw30Tf0uBTthBUlkB0i/0y9uUH/5O8gE2bNln/odwQ+x07dth0oE4C3T/2oSst+Z/pOpnISZwoPHHobCATUVyYMmWKDfuiIi0+rTHvf5H+NuEnC1Ea4W3ciOpL1xEHpJAoQBm8531YrVq1svtlC5WXY4k66Je7Yy44L9eg4NkHUcnlFyeXMDsYZ0BcuBatpr81JQIgn3F09qECcH+E84T/3bt3T43/4RO0ll988YW599577XWokLTuLVq08M5obOPEdbgePoQzS/mxvzh3VBABupMIO9fmnETp3K+Me5JG1OsOK1CxyQu2SeOJ2MoYHZHfoEGDTijvf/3rX7ZsSKMcGXtr1KiRd9aKiku+ET3OmjXLppFv7M+S6xAEecY9yLm4Dvd51llnWXvlPhEV1y83b95s09kXe6lT7hgdPkZesZ2yIc9KSkrMSy+9ZK8hdVg+AX+gfLkXGqfHH388lf+ch8bJbXijUG/Lli1lUV9qhRPIrzZ+CGllgBolpc9JZCBpYZDhElJibBhybXCFTo6ncLLtAlXHC73kPrERW+NEXzZXe6hLdtJQBL1sLidxqi2oONU8VJxqF+nEKZZf65TsIXpkjC5uYVKU2oaKk6IoiUTFSVGURKLipChKIlFxUhQlkag4KYqSSFScFEVJJCpOiqIkEvsQpvddURSlykn7hDh/xqyL8B+w2mR7bbMniLpgI9QlO/UJcUVRahQqToqiJBIVJ0VREomKk6IoiUTFSVGURKLipChKIimIOPFCNV5ZumTJEi+l8FTHNRVFKRwZxYmXlF911VWpdyQzRZC7sE2mA8oFXrvL+6ZXrVpl1xEX/zVuvPFGex1Zz/ea1QH28e7q2ghlVtsbBXk9dE3zu6jQyFMf+axu0ooTN/jggw+aAQMG2Begw7Rp0+xMHCzPPPOMTQtj+vTplUQmqHJu2LDBfsqMKiNHjrQvWkeQeJUt13j++efNa6+9Fts140QiNq7FZ1ihfvzxx5XebS6izHFJFltpnKTx8IMdzJc2dOhQL6WCTMclCbdBDBNZJg9l9hl3YgT3OMqSvEgq2fobD0VecMEFqff9u8ely59CkFac5s2bZ2edYAYOmUjArfy33HKLTQvDFTKWiRMnelv+y4oVK2xmyPlxZmZ9QJCYhYNrRMmQbK4ZFxTcU089Ze6//357LT5Z9zspgtW8efNKjs2replGh+PI59mzZyeitXKhLKRxCoNKywwu7uQV2RyXFLhXxFX8he9BgrplyxZz6aWXemsV4kvDSkPKcfhw0IQfSSFbf/v8888rNTTYhG0ch63YXFUNaVpxomKzEH3ceeeddgqZsMiJAhXRYmodponxRzH+Qidzdu/efUKre+2115rf/OY39lp8hpHLNeOEigmdO3eu9CnpAlOSn3nmmd7af+2WvydQsTt27GhbraSAwH722WdWbLm3MJh+vGfPnt5a9sclBRrHiy++2Fsz9jtpLpQX05FL+QJzscl0/EJSJyTI1t8QncOHD1dqaAYPHmx7MwKNbK7z0EUl45gTlVtaBCqdP3IizZ1/C8ES8QoSMRcyh0xyMwNwhCNHjtjvf/zjH+13CS2DorUo14wT5oKjsMRB+WTdneGUykpr7P5Piu3M4+Y6NvO/MRNFUuDerr/++kr36Aenx5ndSpvNcUmBsuH+3crGd9Lc6Bc/pXxcm/BZ1qWBBCbSTCLZ+tvatWvNueee661VIGVLgDJ69Gg7NOGvr4UirTihpHRVmHfuiSeeqFT5CfFGjBhhx4Zy6TpR+EyS6bZaAtM8M4kfik30JEjUxviT20VKMkHdntoClZbyqwlClA/+ro4LgoRPQlWOx8QN9ZEgIGw2ber4ggULzMsvv5yMbh0RkXRRiGAkYmJhXGjp0qV2bMgtFCIbdz+WoGiH8x48eDDwn9ecl/NzLJFaJrK9Ztz4W9mgltjf7QG2Hzp0qFLrTHRVk+Yp497p/tTkf84jqv5I1x8NB3V1gqDsKMMkko2/MZbUrFmztA1NUH4VkoxjThK5MJhGiCfRixs5EeFICxK0cAzHupWWEHLYsGGBhc55ZaDRjZwEQkyWqNeMGwl5RcDlU9KDuj2AzW6f3z8mUBPAVhy1pkeE/jEm/xhUUFcHaJDdX4LpItFVSiLZ+Bu/Jp9zzjneWgWIGcMpMm4b1PgWkoxjTgKGMDc+o/5BYR0G8BMl86QjWCgxhlGAhMR0DfmFAAM5fuHChSdkhpBt5BTlmoWAluS2226zv0xxr3yyLq0PA+H+sQqBvKRby3Fjx44148ePT1xFpwJyf0THRKLkreQlUXVQpYV0xyUNGjjKiPtl4buMHVGJ//3vfwc2GjJILMcRibgDx0kjnb9RH/fs2XNCI4rf8oPUzJkz7XHUycsvv7zqhlR42Vw6Fi9eXFZe8cvKQzm78P3FF18sKyoqKhs0aJDdXq7Idr3ciLLi4uKyqVOn2u8fffSR3YdP9pPv6WA7x3Me4DgWzsfxspRXjryvmcn2mkZtsyeIumAj1CU7S0tLvbXK6Jswa5Httc2eIOqCjVCX7NQ3YSqKUqNQcVIUJZGoOCmKkkhUnBRFSSQqToqiJBIVJ0VREomKk6IoiUTFSVGURGIfwvS+K4qiVDlhD2FacapJ/4aPE/6sWZtsr232BFEXbIS6ZKc+Ia4oSo1CxUlRlESi4qQoSiJRcVIUJZGoOCmKkkhUnBRFSSQqToqiJJKCPufEjL3AtOIC755evHixeeyxx+w7jHm3NHPQp5stlfcWT5kyJfBd3PmQ7lmSd3e+axZsWWAOHz/speRO80bNzeieo81POv/ESykMVWFPVdkSRqbnf9TOaCTBzip9zokXw/NCdV6aft5555khQ4aklkceecSsX7/eXHnllXZGF5lOZ8yYMWblypXmySefNJ06dTIvvPCCXSe9OohLmIDzcL6oSD5K3q1evdrbEp247MnVFmHr1q223F1bJA0bsRe7cyUpdmIfNmGbQJqU5QMPPJDXpA9JsZMAxG8LaWKnO+FuVArWrSPaIRq6++67zT333GOFhoXv/fr1M2+88YadDUKm05k/f741ZsKECWbXrl12Uk3WSa8O4ih4l1zOh0ATdZJv5BcRZ64VN057cj0XlfPhhx82/fv391IqBHju3Llmzpw51k7sxe5cSYKdVEj81rUTkVq2bJl5++23rZ3MZsKsQblS3XYiRogSE3Eym7CA7d26dbM2YuumTZsqCXQUCiJOdNeYsgmBuvXWW+3EkkzKidi4kROt5P79++0xSYucCo1ERdKy8OlGDRQ+Ak3kKXTo0CH2rm1cuJGCOK5064G0zZs322m7sEPAXneqbEJ8Iu5cRbjQuOXkL0Mgrbi42IqwW2mZiNKdtPLss8+2FdeNOJKCv/yCosCNGzeaUaNGmWuvvdZLqWDbtm2ma9eu9ju29u7d26xbt86uR6Ug4oQRVCwip6efftq899579iYRG3dhDrzWrVvbY5IWOYXRt21fM/OnM82U86d4KcZc3OVi8+ywZ828K+bZxd0WBgKO/YCdFCrrMpcYBStjcjjK5MmTbZ7ELU5y7zf3u9lLMeaaXteYv/7sryl73G1hIKI0KERBl112mXVcd6yR+2auff/9Y6M7G63MiRi3ndiAndgrUE5io39bGEVFRXa8lPK46aabzNSpU22agD3Y6YeJKIkyxE4qbKYZdnMBm/BP/FR49OJHU3b6twXBPeFzF110kfVNInbKtkePHt4eFeXtNpwCUdP27dvtd2xlglsRq6gURJwwgi4bXTiiJ8I7bhBD3YUMAD5FsPyREwvb4y7EXBnSeYhp2rCp6daym3VmCvq6M68z7+9634z937F2WfPtGm/vzEjB4QhBiKNQIWbMmBF7RPGTLhUDoX3a9bG2YNOw04aZ1798PWXP9sMVzpYJ7pWoiG47EVA2UJkRMiJpfILGifU4yxu7+rfvb0rKSlL2IlZdmncxv/vgd9bGP63+k03PBu6NcqPbhq9mA3WCBhrhxk66sdgcJ5Qdfol/4qcgDaWU5cufv2zXswFBxT66oNmWx/Dhw60gYSO2Qp8+fexnVAoiTtLaI0oHDx60v8YR0stYE4KDcMGaNWtSYiXO6UZOshBaJoFeJ/cyXx/62pSUlpg+bfqYPm37mONlx83KnSu9PYz5+9a/e9/Sg01EleQHn+lsxDnoJsQpTlRaKujG7zaapg2aWluw6cCxA2bh5oXeXtnbQzcAkY0qpLTA0jDRjQ9qkfMBuxrWb2g+//5zay92U46ffPuJ2bBvg92HzxU7/jsteRj49qxZs8y4cePswneJhjJBhCW+T9TlRiJxQNnhl/gn9mHnKc1OMR/s/sDbw1gbxeZ00Pt55ZVXUuN/btc1Hfip1H26guRRrg1NwcQJUerSpYtp2bKlrVTffPONt7UyAwYMsAWGaCFeLhJ1sT1uh80FWqZWjVuZ9XvXmx2Hd1gHaHNSG9OoXiNvj+yh4iJIOCnQBULApULzyY8J0s8nT+n+SLcvDqTSEvUhSGeefKZp37S9tzUaCCshPeXEPU6aNMm8+eab3tbMYCddeBqluMEu7MNO7B3adahp1rCZtzUaDGIPGzbMCgsLYy74Z7aQT0QWRBhxgz/il/gnfnphpwttoxMVfI36ePPNN1thQVTpgrpjTpkgMiRSzEeACyJOVCzmXZdf4m6//XbbospAOJEQA+MCLS7phPPSrcM4wFmjZEohoWVq2bil+WXPX5p+7fqZjs06mhaNW1iHp6JHgQqMILmtCmMVIj58Tpw40dx11102vxAxWqE4xYlKiz23nXOb6dqiq+nZuqc5+uNR69jZjL+4IEqZxl5ofbEFESJCpoWlIlBhKWeipjjtA4kOsQ87sbdHqx6pxiUq2Og2lFQ+6b4I+DNpDG1glwwsY/9DDz2UVzQRBuXVrkk765f4J3bin9LoRIF7wzfdssAeV2io4/wYgH3YyXbKkfKkXPlRI18BLuhDmBQGrQQPUDK6TyHJw5eyrV27dmbv3r2phywxkAJ8/PHHbWYgTFRQDHUHWOMg3YNu498Z732rgMIf12ecbX2fW/+cTWOgEQibi04vsiIF2w9tN1NWnDgoPvvS2d63whDFHga9R3QfYZZ+tdR24ajEVF4q7bfF35qfnvpTb09jW+JHP6ywVSi0LWFkejjRbydjLojTU2ufst0Z1+7BHQdb0QK6Q4yzud1ZqCl2ii+K3zGmRuT05tdvmks6X2LaNGlj04+WHDVzN849oQtbnXbqmzADiFKZ4yBJ4pQvNaXS5ovaWVjSiVNBunW1AR7rj5O4zxeVOK9f3bakQ+2MTlLtVHEKgf8bxVVonIfzVSdx2ZMEW9KhdkYjyXZqt64W2V7b7AmiLtgIdclO7dYpilKj0Mgpje0l25aZkk3zTdmxQ15KdOrxqEHvMaZht2FeSuHQyKnmlVkYdclOjZxyIN/CB47nPLkgz5LwbJD/j5dKMNVdZgKPxASVWVh6VKrbTnmeCd9kwa506bmg4pSGfAtfyPU8/HWAZ7t4Apnnvvg7AYWvhFPdZQY8w+d/ZQqEpedCddvJk/L8507+3SGv8wlLzwUVp2pCoiIcFviUV3EAn7/4xS9STyPz4Kr7732lenDLyV+GQFrQK1PC0pOIRD/yZLs/2mN7r169Uv8I4OFpbNq9e3dgOrbngopTBBqe0t+0/Pkc0/rqxXZpfsl0m95y+KxUWquRL5lG3S616elAbNK9MoVP+fsP8CoR/vEv25XsaTrw9hPKp0nfG0zrXy5MpUtZZoKKl8srU8LS4wQbxB78FH9107AXuzOBqCBOYa9MYTv/mxP4oz7gr0Hp2b65wY+KU1RKj5sfNr1sjnw4wzQ4+fRUYZfsWWP2LxplDiy53hzf9o5Ny4ZMr0wBWqxC/Sm2rlB64GtbPj/u+8w0+Z9rbFpZyRFbjqQfXj7NpmUDlTPqK1OqCvFDc/yIOemsihfBie37X73GHN2Q/VtGs3llClERLxDkD9DuPmHpUVBxyoOyH4+bHw/t9NaiQ7ic6ZUpCBOFfN9992nUFBOlR/d536JDlybXV6ZUNaVH9njfooPfZXplCgLE/2D5g7r/T8FB6VFRcYpK/UbmpN7XmWblXYXjX72VipIadhgQqXtAAaZ7ZQqoMMVH/Van2fKp36RtKkqq17CZaXb+pKy74pDvK1MKjfghAly8apZNE9sZfsgGxDbTK1MKLUygzzmlsb349cpjBPThmw6cYI5//X+mUZch1gFwdApdvofRtCjaDBc4Am9jkH47EGLL2xqC0OecTiwzYMypYdve5viOlabxGT83xZ/MMQ1adE59D+uGRy0zgYFkuuECr4Kh8QlLDyIXO6VhJGJq2HGgKS7vstK1Q5APvnW73RZEVDsRIMbceAWSy+9//3vzt7/97YR0XoMU9j62dM85qTjlKE5055qee6spO/Kt3UbrBGUlxab446dPcPhcHT0KKk7pxYkKSgVu2L6f+XHfp6ZB27PKC67iNTeM1fgbl6ooszDyESdpMOs1a18uVN+aBp5vmtIS88NnC08Yd6puO1WcAsjFAXJFxSkealuZhVGX7NQnxHOAx/vjIK7zKJmpK2VWF+xUcUoD/zvKt/A4nvMoVUNdKbO6YKd262qR7dqtqz3UJTu1W6coSo1CxUlRlESi4qQoSiKpX473VVEUJTnUb9CggSktLfVWFUVRqgZ0p1Gj8Nmy6+3fv7+Mx9FLSkq8JEVRlMLTsGFD+5/Rli1bBj8hXq5eZceOHbPiVFZW5iUriqIUDsQIcWrcuHGgMEG9ckECb1VRFKXqCBMmsOLkfVcURUkM+lOdoiiJRMVJUZQEYsz/AzJ3DMGbKXmjAAAAAElFTkSuQmCC)
ちなみにREの内容はlist index out of range
で、dp
配列のサイズを小課題1の制約(10000 × 30)に合わせているからです。
ではdp = [[0]*B for _ in range(N+1)]
とするとどうなるかというと、タイムアウトになります。
解説の理解
正直、解説を読んでも桁DPでググってもよく分かりませんでした😇
なので想定コードを解読しながら何をやっているのか理解しようと試みます。
1つ目のテストケースを例に考えます。
1, 4, 9だけを使った3桁の数の中で、7の倍数はいくつあるか。
N, B, K, c = test_data[0]["in"]
N, B, K, c
まずはdp
配列を作ります。
ここでdp[0][0] = 1
としている理由はすぐに明らかになります。
mod = 1_000_000_007
dp = [[0]*B for _ in range(N+1)]
dp[0][0] = 1
from pprint import *
pp(dp)
最も外側のループを1回ずつ回して確認していきます。
ここで桁数だけ繰り返しているので、「各桁についてなんかやってんだな」と推測できます。
# for i in range(N):
i = 0
for j in range(B):
for k in c:
nex = (10 * j + k) % B
dp[i+1][nex] += dp[i][j]
dp[i+1][nex] %= mod
pp(dp)
さて、ここで何をやっているのかというと、以下のように100の位が1, 4, 9だった場合の余りを求めているのです。
![](data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAATMAAABbCAYAAAAfiGLdAAAAAXNSR0IArs4c6QAAAARnQU1BAACxjwv8YQUAAAAJcEhZcwAAFiUAABYlAUlSJPAAABAWSURBVHhe7d1xbBNZfgfwb1ru5FS5yqgg2RXosAQSjnYrnB5dbB1/rK9RFUcg4QgqHC0S59ztgXNUxTkkiFu1rA0tGy9aFoNuLwZ1V3HaRTbSojjqoUxOy8pmC4qR2MasEjGRiGRriRpLRMpI5Tp9Y16ywCUk8YzJePL7SCbznqPZzZt5v3l+M36/OpkBIYTUuD/iPwkhpKZRMCOEGIL+g9lUFtFjISQG00ic6kT0yxJ/g+iDhHx/CJ3nUxCuR9F5KoH8DH+L6IiE7HsuRG7zogHpfM5MRNzThtKZEQR3KOUcoo4QzNcG4N9a/gWyyqThEGyfNiF/xQszK5eud8B+xwfxjBumZ79CVpWE4t00kp/1IfZ+Cu1ZGd27+FsGo++R2bjARmRuOLbzMuxwNLMR2rDIy2R1ScgMRtDodJQDmcL8phONZ9PISLyCrDITLD/yInCuC+28xqh0HcwkMQ8B61E/f4k3of4HgDAmsm6klnLFykLU9FNrCfnhHIpPedHwChDvsQDWUM/LjKmeBbYcxEleVkGazCE7ru20QjX2uXZV43yvfJ+6DmalqUVGYBNF9idXTppRQmEJwjkvEuNKhaQ6OErleaI8Uu4eZKbYZvm/YXRFFG/yzRcIKCptUCl+PEq3wvBeU84BVlZ9gKqwzzWsGue72n2uvbuZT1ljHW/FT44JmLa4YBqLoO1tP+L3VByMooDoTxvRel6EqcWK6eFOtB4IIa3B6GQtyl9j7efuhFCywmXKI3LADf/VnKoLTjX2uWZV43zXYp/KDQC9mv48IANhOcPLisxpyDgyIE/zcqVmc72ybztk9+mM6n3NKfy2W3bDLvs+GeU1Rjci9+yA7E0UeJl51Cd74ZB7crxcqScjcu87dhlvs+P/mNepVY191oyMHGbdPZzlRQ1U43xXs09dj8zMdgfcKGB6/jNlCdMFwLHNOj/hvHIi0ida0XpJQpPTC8+mAbQ72xH/mr9diZkcYr6fwH97PZzNHrifRuHysKtKkb9vWMoNGdaiRXZQ5kwVWAu7YN/CyxUQb3ShdW8M0psuePdYMHDIhfbf5Pm7lanGPtesapzvWuyTBzWdeij3tjx/lVdGAh65d4wXKzQ7Pcv+Lch9+y1y+E65Qi5XVWxWni7vQLn6+eSkMlB5Mi3P/m/5TUObFbply+Hk/Oh2OuWXLSeHWIuowNuukPDKljMjrGKufVWoxj5ripYjs2qc7+r3+cf/xPC4pkPr0fQ32zD8L3FMrpPwX7/5BKVf/Bp/t1PdE0zrTOuUf/H06UZs/ssmbP5TE8pVFVsHU3kH38PTH26Efec2rP8TE9atgRnJdTYXWv/n3/DPv5tBQzGN6M1t+PXpNli/z3+hEt9/1nbrfv97bNz8V2ja1MDbV4Vq7LNGlB4IyNy6hc/+Q8CjH/4FrP/HepZto4rnAKtxvqvfp84fmiWEkOVZA2MHQshaQMGMEGIIFMwIIYZAwYwQYggUzAghhqD6bubQ0BCSySQvkZW4dOkS36quo0eP8i2yEocOHcKuXdVfL+fDDz/EN998w0tkJZ7vQ5oEs/++eQFXv9qEtgNv4M94PVnakSNH+FZ1Xb78r7j36b9j6u3D+OtN3+O1ZCkOh+O1BLPLly/g0X9eRebP2/C3b1IPWonn+5Bmz5mJ/e3omOjCwEkHLcqnRzNZRPZehP2TPng38TqiIyIShzogHhtA94+oB1VCszkz28EYgo+6EL1L6xDoUoMT3R80IXYqBcN/ZbQm2eD7IIjCiShy1IUqouENADM8x33I/DKGHK8hOrMjgG5LF8I3aHFCXdrgQfBgBoHL1IMqoe3dzK1t8Nt7kBymS4s+meD2BZC5nGQfaoge2fb50XguCYG60Ipp/GgGG50dbEfk07SqlWBJFe3wIvA0htQ9Xib6wkZnvnciSAxSD1qpFQSzHKKeCLJLXDFMO90IXBWQ0fhYKDcY2vtptudVSjc60bFkG9nQ1AL0DVfho8xMFiEHO0d4kbzkXhStZ7NLrG5rQtPuAOI3M9oNCJS1wn7agWh/DJ1HExANOupbfjCTplEYDMFVX4e6uu9e1kMvTSib7XDti0G4o02LlR6kkXi/Ax3HE7TE8RKmi3nEfdYXjk9dnQuRl27KOHZ6kBsc0fijpoTcR0FEaMS3KOlxAelTLtS/cHysaL/24gXIrCwgeVnAiCYnvITsOT/Su7sRPBhAaHcS7Qadk1t+MCsWIX38UFnMkb9mMXTSj9gZLyz8V56xweYAhK+1WcXTvJ0Nu38Vhn83ryCLKj5yYGh27viw11gv/GdiCL58q39LI7w3c8hrOXoe70Myb+UFspBCUULv2HPH58kQug/HEN3/Yg/CFjZ6hoDcA15WQRoOw/teE/x7bOWyZXcbrMf7DDknt/xg1uBAYN+zBlGI/SFk915c8Jkl21YvcmMFnc+bGS3VnASbrwuuubilPFd2qR7dCz33t0npLBnkJ3hZNRGJK4D/5028rA2jpZpbvzOAtvnk1azN/jGL1gsvDwYUbECwPwfxkfr/z/ztOPvkZIN1A69YZ2LnQx+yapaJn1erqeY22GGfa5DJFCL3PQjuWvjhPlMDu0JPlXT7sdCYqeZMsGy38MClfOSLw3LUx07jhbATekdOs1RrpRtxTB/ww6bVwq3VSAtXjX2ukHm7fT53RfFaBKMtQTgbeMULTDCzvlbQ4Bwyb2jkW1y5HYoYFdXNPxsk1ZwE4VIXbHsXT79v3siC2S0Rz6W50I+1kGqOfeQL5dxonR8FvMwK6zZg9JEGN1RmBMQetMG/g5c1YPhUc5KAi6dsaG1etAdhPetCmQn1PcjWEoDPksGoctFmSjkBKfZTUjOaMkyqucdJ2T+XcGAx2fAfpIhTR0k+8lJKM5WMnGpu5JyDJ+1YjFbtOStnTofloSe8qOVxN3CqOSXpC95JsqOwuHJKRXZuamE23yd3/7JHTqZ75Z7TQdmrUWKTmk81V8oKiKMR1j/8oF8jjJ5qLgchkYNry2uYjJ/JQzRbIF6LI36VvdIjrHIEA2w7q+IqbexUcyVkbsaBbdYF5sqqw7Tdh/CFILwtfgRb1iNj6YZTzUjaKKnmHn7sXvrqq1yhLWH5VWODldF2ZGboVHOzQ3KQHdZXt9Wz9vR9pk17ztNqZGboVHMP5d7mpUddysjs1aPrZbp/UXbCJgd/++xvVUbtno8flrcrp89UcysemUnSLLDL/MokvKXH7LP+bhu0GBsod5+EwQFkxtjV9dYA0sqdDpUTHSazMldhhn1fGG4lWa2J/T2LTV8siwnm8g5scF5ph0NpnAazyvR1FVImeC0WWF/5BxVQYO3ZuFmrsYFyZ1hA4vMBtj2CzKCAvDKBWynedmZ7G8JvK7cw5tpXhWrssyLs+DwBnOZX9qBysmtNRtdveBA67YW1lEHqoy4kN/Uh+bOFbwstXzXOd/X71GwJoOcV+9tgveXH9CXPK4MeWS1ZROoCMOVGENRw4p5opYjEASsy70zj4h7qQctVwd3MpYnjKTi2WSmQ6dWkyMZPLtiVUSnRIRHiNQdsm6kHrUQVghk7EDnA/Yadl4nuTIwi1eyAnfqKPk0oFxs3HNt5mSyL9sGslEfmuhdN9tWYjyDLkbuThmV34yIP1JLVVrqfQWp/ExqpC62I5sFMuiMgtr8NblqaWafYVX+wgM5mJy8TfZEwcisG7z73a3t0wyg0DmYlpPuj8B/00IHQq3spxB53wVP9PB2kElPKKjF+tDdTD1opbYPZeBLxfA8C+2gyRp8kCIkYXKf9cPAaoi/i9ThGPwjAO/c9aLJsGgazIlKn43C8H6COolPS3ShCE2EE6Xa/Pk2mELriQPRn1IMqoVkwE/uDiG1jneXHNGupSzNZRE+MovPcYitpkNUlInEqhsbzoUVW0iBL0SSYSXcj6Mq2o/cfnKBQpkds1HysB6YP4vDRs2U6JCF3tguZ/b3oXmRZLbK0qnwDgBBCXjeN72YSQsjqoGBGCDEECmaEEEOgYEYIMQQKZoQQQ9B/MJvKInoshMRgGolTnYh+qe8EdmuPhHx/CJ3nUxCuR9F5KoF8OcsO0Yccop4IsquSueU1Ux7N0K+Hcm+LQ+7J8aI8Ivfs8Mi9Y7xIVt2s0C1bDifnk8IoyTosJ4fk1ViQmiyAL6OudPXnX5YlEqrUIn2PzMYFNiJ7fl0nOxzNbIQ2rOQ9JKtPQmYwgkanY34hTvObTjSeTSOzFkYCtaBYhPTxw++yqMuzGDrpR+zMQsmHa5uug5kk5iFgPernH4o2of4HgDAmsm5EVl8B4j0WwBrqeZkx1bPAloO4WjlDyYsaHAjs++4LbGJ/CNm9F+E14BJdug5mpalFRmATRdDMmR4UUbzJN18goKgmoQnRzgY77HMrcEymELnvQdCgX5miu5mErAkShEtdsO11G/b707oOZqaGRVJtbTDTF9p1wQTTgtmdHDDRAdIXZdHHs05DJ7HRdTAz2x1wo4Dp+c+Uz/IJUuYnvVBuyABikR2UOVMFiJT5SXdKWQFxNMJq4AVs9f0xc6sbvpYM8hO8zLpJPutBYA8tXqcPJrhaulG4L87PYZbEPAonvXDT1UZXpot5vmVc+l8CaEpA5JQA2z4XZodTKDb3oLuZeop+SMhfDSFacsG3RUTiphnBc37YaYFBXcl/5EJjoh2j2QAbTxsTrWdGCDEEuptJCDEECmaEEEOgYEYIMQQKZoQQQ6BgRggxhFW/m/nVV1/xLe289dZbfIuoVY3jo6BjpA1RFPHtt9/yknZq8fisejDbtWsX39LO7du3+RZR68SJE/jiiy94SRvvvvsuDh8+zEtEDSWYHTx4kJe0U4t9iJ4zI4QYAs2ZEUIMgYIZIcQQKJgRQgyBghkhxBAomBFCDKFmgpnY3472/iIvEV2aySLkiCDLi0QfpAcpRM8nkLrahVZfFFmD5mfQfTArPUgj8X4HOo4nKCOTrknIfRRE5B4vEn2QsohekND+9z54D/cgvDMJ154ocvxtI9F9MDNv98D3qzD8u3kF0afxPiTzi+RsIKtGupWEsMEynzPDsccP9+0uJL/kFQZCc2ZEAyISVwD/z5t4meiF9FTC6Hsh9H3NK8p5TYH8I+NN2VAwI6qVbsQxfcAP2zpeQXTD3HIRBTmDwBu8opxwxgGX3XiZTSiYEXVmBMQetMG/YMo5oje5m30oHAkb8nhRMCMqSMiez8J5xEF5TGvBeBzh+13IXPAYMlUjBTNSuZk8RLMF4rU44lfZKz3CKkcwwLazk89+hejERAId5+rRc8Vn2OmAGlk1o4jEASuS+wpIHjRwFtNadzuCOieQkbvBfhCdkO7FEM660MVG0OURGTtOkafd6P5x+W3D0P3ITJrMQRgcQGYMEG8NID2cQ5EeONMZCcW7AhKfD7DtEWQGBeQN+mBmrZHuRtHa0onI0Sasr6tDnfJyjsK+lf+CgdB6ZoQQQ6A5M0KIIVAwI4QYAgUzQoghUDAjhBgA8P+fEe/FxlKJrQAAAABJRU5ErkJggg==)
という訳で、dp
配列のインデックス1は100の位(右から3桁目)について、余りが0~6の場合の個数を持ってるんだなと分かります。
そしてdp[0][0] = 1
の理由は、100の位を考えるときに1,000の位の余りは0であることを表しています。
ここらへんがまだちょっと分かりづらいのでループをもう一周回しましょう。
# for i in range(N):
i = 1
for j in range(B):
for k in c:
nex = (10 * j + k) % B
dp[i+1][nex] += dp[i][j]
dp[i+1][nex] %= mod
pp(dp)
上で見た通り、100の位の余りは[1, 2, 4]の3パターンが1つずつでした。
それぞれのパターンについて、今度は10の位(右から2桁目)が1, 4, 9の場合の余りを求めます。
100の位の余りが1
![](data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAATAAAACOCAYAAAC2TFRCAAAAAXNSR0IArs4c6QAAAARnQU1BAACxjwv8YQUAAAAJcEhZcwAAFiUAABYlAUlSJPAAABSTSURBVHhe7d1/aBtnmgfwr7fZq1zcq3wkhwQJG5WGtUL3LvK1Ryw2f1QhBcuXcJFJIBLpkchdSOWWXuSaa+yUI5FbcKyUTaMWulYNKZK5BinQYKXUeHyse1IgqWRosQIJGXMOSBCDVRrOw67p3Iz8OmnSJI6tkfWO9HxA8bwzYRjrfd9n3vnh96mTFSCEEB36FftJCCG6QwGMEKJbFMAIIbpFAYwQoltVH8DEYQ88w3lWIvwoIPVRH0IX4+hzt6FrOAuJbSF8kK7FEfwwivhQF9rcQaRm2QaeqE8hq9FcdkSO9HtlhwmyK5pjawkvclGfHEjNLxZuj8g+k0n2fTm3WCaVN5+UA0ci8lLPSZ9ukbF9QE6zMi+qdgRmbHLC/U4A3h1sBeGIiJEhCSYTK653wHUwj9BQQtlCeCBNxCCsN8HAyrbdXjgudyH2DVvBCY4CmIT81RTEAityq4DseAb5BVasJbNZCJNaXI5LkH4Mo/e0oHybKgPqn1V+XBChyd5vZZC6wX1DKgPt2qa0IGHqZC8i37MVhnoYlR/ZGS1qSLvj5CKASXfUux8FCP0uRG+oK5QGXtzCF+mO+m8WcccAkur9gOJx1wClMUtqY7sRx87TyWKQWfwuVssKX0pG7oyz2CnUup/LKT+O2JQtJWDtpjARgOu8OpZTyjVSRVq3TWPrWeTkJHwvshWzOWV0bIPdujRsXh2tj7PyAWxB+WWOtmHnWwLmTHYYrveh/RUvwpOctby8gODhrWj7UISh1Yy58U607e9F4hbbXsXyE0F4bG0IXjfAaZqD8FYb2k8kNBktFc0KiH/SgoE/LAW01cmeV+rE0QmhYIbdkEXffge8QxkuT4aaWoO2mRmNIHckAO82tmI1ynGc7F5Yxc1nBmV3E2THiaSs3a3cnBzZp+1N/NzXPbIDVtl9boqtqRF/zcljxx0ymtxyJMvWaWJeHnvHIQcmNKr1H9Py4EGrjFcCcvI2W1cjytY2rw/KroMR+eZfWblEWh4nB5eQIhLdbWj7WEJziwvOjSPwtHgQXrr25sWdDELunfBebkTLLiccC0HYncrZQ7NhCL+kyRA8r3qRamyBY7cD8/12tB3TYgRWQOoDZb97Yuj5fSljr0XixS607QlB+p0drt0mjLxmh+dPWba1ipWzbU5H0dFfj4HP3LCsY+tWqxzHyQJZRc3PqY/T1dGSSQ5cKa6Qi6tKpuUIbF6eKx5UUg7ALcfUXf44J89rdFbi2lJ9pAIyDsaKj9YX66wUN+WREwE5JrKiWlfHlbM8K60Kq49c1CWb3lcf+C/VWbUrT9ucz5yVez5O37siUuo/MMGWV0X74+ToPbB5OR0d1GzYPz+TlscSg7JvG2TbkUF5REjLOU3asnIp9dmIfLMW+sWDZsbkwS9vKjVVqpwcO2RRZ0G577MYdEo3n4nIg6lafKdMu7Y5f2Wg+A7l/XXEgk7JtDtOmk6HEKJbVfsiKyGk+lEAI4ToFgUwQohuUQAjhOgWBTBCiG490VPIH374gS2RlXruuefYUnlRHa3eWtQR1c/qPa5+niiAjY2Nof1f/wX/95enYKhfR8O2J/T8888jnU6zUnk1Nb2AGfF/8dPfPIOnn2IrybK++uorbN++nZXK549/HEDvfxzDX35lQP2vqQc9qT179uDcuXOs9Esreg9Mnd20Y7oLI+/a7s4TRDhyJ4W+PWdhPReBayNbRzgiIvpaB8S3RtDzEvUgLazoVGA5EIJ/pgvBqzUyR4neNLSg53QzQsfi2s0UQTRkgfu0H7nuIDLUhTSxwrGsEc6jbiTfDCHD1hDObPOhx9SFwMVanNBPB9Y74T+QhO8T6kFaWPnF+Avt8FoHEBunUwifDHC4fUh+EqPpmTll2evF1v4YBOpCJVvF3URlFHbAg77PE6BzPKe2ueBbCCE+ycqEL8oozH2wD9FL1INKtarHIYaXHfANCUjS988pC5pbgcg4XabwyYDmHT6ER5M0CCjRAwEsg6CzD6nlhrZGK+x7QxCu8D8Grra8kIWLneh4gt/H9rITmUtpfVxGTkfRvj9aHQ8eJoNo+yC17DTWRnXSxU8EpHnuQuoEhIc7EBwOofONKEQOj/X+ACbNIXepF/b6OtTV3fuYX3vwqZYFFhsgfM/vbJeFawlET3Wg42i0quZEn8tnEXab76ufujo7+h58Mrx5K1yjGWS5P8XnEX/Pjzgr6Z10O4fEMTvq76sfMzznHwjPm5VRMgRkrrEydySk+r1I7OiB/4APvTti8HD44OH+AJbPQ/r0pjrJIfvMY+xdL0Lvu/BgLhLLCy5krue4HQJXa17I/IwNY/NL9aN8rg/C+34I/gffK9qodpAkstOszClpNIwEtrKS/uXyEgav/6x+fhxDz6EQgvt+0YNg2ZeBOMNnD5LGA3CdbIZ3t6VYNu1oh/lohLsHD/cHsAYbfHsXD1glDvcitefsQ1+KNDSYgdmChqMbygu5PAkWdxfsS7FKfXH143r0PPTFYgMM2zLaphXTLC8koxx/8HIL/K2lz4f/c5XMC9n4sg/tL7CC+uLqeym0nfnlAECtH+N6JeBpmppPu7aZvRxWxsYWmJVjLFqntCdEkNIkV0W58kKut8K6dMC34uj7zgn/9oe/MWzcoASwCRFqOr9SUV7IJ2WAqWkpW7KEzEdhmN5wK83sYcwwbwGmtEhEqnleyEWZoRHYjjjQyMol4yAvpLHJejc1XP58H6Za/WhpYCvuY0Sj0oWS01r0IO3bpnH9A6Pi4nebx5RYWntao7yQEoSPu2DZ42Cd5RGU36Xk9kF5IVfnRgS9GQfa7p7tH64YeEpUlryQN8KImTrhXDphaoCrvJCSgLPHLGjb9dgepIxCNDi6MrRNS6sPblMSU+qAQlHICMX7lCW1pzXLC3k7JnuXm8BfzVCDgJxkxVJRXsiVSffblkmCofHvrmleyJty5N3BuxmI1CxC2BdRjlgDnOSFnIt772ZwepTkCchQ2rtWtG6b89mI3PPmgBxLDMoDJ/yySwkXgRTbWIKy54UspASEsRXm5bKIK9sff355EpQXcuUyEKIZ2Dcr1yDLMJSay0+heV7I6SzmlEMXhsIIK5/IhHIZNZNEZCiBbAmXpvzkhSwgORoGtpgfcu/rfqZ1pfegcrVNQ5MbgTN+uFq98Lc2ImnqQUspmbnXKi/kzU+VM+0yo6u5L32anTUpL+QKzY/JfqXqHv97peWBbdqcMcuTF/IezUZg3OSFvCkP7lpudDUnjxzhuG1+d1ZugUX2f734/akjfuenJWXtVGh/nA8dgUnSPLDdePdm5MNId5Sz5nqjBiMwJdIb1b0YYd0bgGNzcQWKq0qgPokSLo0geV05M0+MIKE+9SjpdoMBxuJBWdDymQc29ctpUH5/DUY4K6beUDWZYH7sl6T8n0kbDNpU0GJ9bGzB4D5bsV0s1lmp1KdRCcQuJYHraQil1hGrD6O1HYFX1EcbS3W21pTv/kegxfjYHoTCLGBu0KSCtG+bLzrRe8IFcyGJ+EddiG2MIPb6wx8XPTntj3NF84H9XOpkHXwNaaT/3cbWEK7ciqJ9UxLeubNwPq4fkQpJoa/OB0MmDX8pl2U17hFPIZcjQswAjhetrEy4Mz2F+C4brBS8+DQtIg0HbE2sTFZldQGskEXyggvN1koMz8mTyFxJwLRj6yPeESOVVvhOuTTb14yt1IVKsqoAJl0RENrXDgdNW8wp5ex+KYfOXS2sTPgiIT0RgmuvY9mnlOTxVhHACkgMB+E94KQvn1eTcYRud8FZ/lwVZDVm1YkGvPDsoh5UqpUHsBsxhLMD8O2lmyt8kiBEQ7Cf8IIer/BJvBDG1GkfXBr+FUKtWmEAyyN+IgzbKR91Dk5JV4PonQ7Av5tOMFy6FUfvZzYEX6cepIUVBTBx2I/QFqWD/J7uPHJJnd2hewqd/Y/6A29SWSKix0LY+mHvI/7Am6zUEwcw6WofulIeDB5v0eTlVaI1ZXT81gAMp8Nwqy8DE85IyHzQheS+QfQ8YoYXsnKrfpGVEEIqbRVPIQkhhA8UwAghukUBjBCiWxTACCG6RQGMEKJbFMAIIbpFAYwQolsUwAghusVRANNLYtsapnViW6KxSiZdrgwuApheEtvWrDIltiXaqXzS5cqofADTS2LbGlaWxLZEO7wlXV5D3PwtpDQZhvdAB/LuJGLHWx6bEYlUwEIewgkPdp43IXIhAjfN5c6d/GgvPK/GYToXQ+RgbeSr4OASUieJbWuY5oltiba4Srq8trgYgUkFCQZjAdH9NojdOfS8WEBBGYNVJKUf+SWJ1cdkH+o+tiJ3zgVjsc6ogvggoVAAjMYM+urOwpqLwNVQgGSoUN7SNfTUfyrYcsWsK37L67CwsAGb/qkZm/7WUPVfvK6sW6qPBWz6Oyv++beNMFAFcWQdq49fY+E3G2B9eQsanzFgXQ28JEXzgRFCdKsGYjQhpFpRACOE6BYFMEKIblEAI4ToFgUwQohuUQAjhOjWmrxG4XK52JJ24vE4WyKl6u7uxo0b6l/Ra2f37t04dOgQK5FSiKIIv9/PStqphj60JgHswoULbEk7e/fuZUukVOWoHxXVkTbUADY5OclK2qmG+qEXWQkhukX3wAghukUBjBCiWxTACCG6RQGMEKJbXAUwcdgDz7C2s7CVY581604KfS19SLGiZqajaN8fpQkSSyYhddKOvsusWCp1osTDHQgOh9D5RhQih7O8cxHACtcSiJ7qQMfRqGbJPMqxz5ol5ZG5EELXYS96teocd+URf88PequvFGpGrzhC3R5439Pq9KIEw34vEjt64D/gQ++OGDyfZNg2fnARwIxNTrjfCcC7g63QQDn2WbMMJtj2+jBw1MNWaEcaDSOBraxEVscA00su+Pq7oFUNSeMBuE42w7vbUiybdrTDfDQCgbPRAN0DI5WjXJIGL7fA30opXHiTvRxWxsYWmNezFeqsvIggxVmuCgpgpGIyQyOwHXGgkZUJP4zrHxgVF3O15jEl8nWnkgIYqYwbYcRMnXAuneEJVyytPrhNSUyxP5EtZITifcpigmOOUAAjFSAi+hng3WdiZcKdjS6Exz0QzwQRvxRG+Hsj1CkZmi181RkFMLL2prOYMwPCkNIxlE9kIgfMJBEZSiBbTJFPeGBociNwxg9Xqxf+1kYkTT1o2cY2coICGFl7m53wvemF99Dix7NDiWab7PAccsLawP4PqazvQ7DXPY+u0cXHjpnxGJpPeOHgLBUoF3khpVsZ/Pl//oyvz3+J736yYtMzdXjWbEZDCakHy7HP2lVAdjyJif/+Al+Mz8Dyj2Ys1DXCsr7U1qzuV0DifAiJ7AY0/3YDNlAdrUrhmoDkxAS++C8BM7/5B5h/AhotG7DqGvr7DTA/dQdSgwF5IQTBFEDo37aAt6qh6XQIIbpFl5CEEN2iAEYI0S0KYIQQ3aIARgjRLQpghBDdogBGCNEtCmCEEN2iAEYI0S0KYIQQ3aIARgjRLQpghBDdogBGCNEtCmCEEN2q0gBWQOKNDkRvsSLRBuWF5JzGeSHvUvb7XnMZ9lu6Kg1gc8jdCMOzqQ51dT/7KJ0vQ0kiV47yQnKuHHkh75GuBuE/yV9OSFWVBrA8xG1jmJdlqNOdqZ+bn3oR+MgPG2czSuoC5YXknPZ5Ie8REflyCmZW4k11BjDJAs9b9ruzUUqX+xBq6EHPSxS9uEJ5Ibknfh4GXutEMyvzpjoDmDJisG5kwUrKIPipCb4DixmGCT8oLyTnZhMIF9rhfYGVOVSll5D3iMO9SO9qA4UvzlBeSM5JEP6URfvrNlbmU5UHsAziZ9Jo3kL5B/lCeSF5J30TROolH/f3jKs7gE0KiEzawVkuTkJ5ITknISsaYboVKdZPWLnUTytr0wll+Ru+Xnap6qxE0mgX6l8VEZmJwb2RrSSrd7kPdS1AUu6B8kMz+eF2mC+0I/eFG3SuKUUKfXV25YeMnu1slSbKtd/SVfUITFqQYDKZYaRkqSVazN8YH00qy0kIFwQI1wqLm0qi7jeB2CVlv9fTEMYzyNN7equi5oVU66VYQ6Nx5bvMKt9u6dT8qsLwCEaU5XQqoVG9a4fyQhJCdKvqn0ISQqoXBTBCiG5RACOE6BYFMEKIblEAI4To1po8hRQEgS3xzeFwsKXaopf6UdViHYmiWPzowVrXz5oEsJ07d7Ilvo2NjbGl2tLd3Y1vv/2Wlfj19ttvY/fu3axUO9Tg1dHRwUr8evrpp5FIJFhpbdB7YIQQ3aJ7YIQQ3aIARgjRLQpghBDdogBGCNEtCmCEEN2qiQAmft6O9mHKOsiXAlKnOtH7eQKJz3vReSqlyfQvRDuFaylkZ9n8RlIBcaWueKuj6g9gt+Lo7aasg7wRhzzwwYvAQSecBwPKkg+eIX28rFkrsuft2LqhvphT9XlXCMZWJ3jLH1XlAUyCoJw18DtWJJwQIQwn4NhmZWXAus2BxLCgbCH86MHY3Bzm5uZxM9EDB4cJWKo6gC0mJvCjjdIO8kUSkR0FGp+9lzHC8GwjMJqFSDOycqQe9UYjjEZ+M3tUcQDLIJywwbeLsg5yZzb/iJGWiPwsWyQcSCJ8MoTEpTC6DnchMc1Wc6RqA5g4FIP5Df6u2QnRC+u+AQwc98HZ6sXAHxrhPRBUhgV8qc4ANh1FeMELF2Ui4lODEWa2eD9KwMITY5P13gBgowX2ywNIXGVlTlRlABOzczCvE1hOuwiSM0BuIoLwxSzoFgsHjFbYdil1cvveQ/nC7RywzQIzDZm5ULjUCbO5E4n73psww7COLXKiBmajyCO634zY3hxiByjrIC/EoTa0zwaQfmcxdX3mVDN618cwcshSLJMKmwyiLWpDpN9RHIVJSkCrP2FBOuXHYo3xoboD2GwWwhVlJHa4E9mDEQzsd8D+kgmcZ0uvEQUIJ7sgbHbBviAgfsuJgeOLnYXwQbzYi9C1rbBvFJEYN8LX74ONswqqgREYIaRaVfV7YISQ6kYBjBCiWxTACCG6RQGMEKJbFMAIIToF/D+/VRvMOQ8zmgAAAABJRU5ErkJggg==)
|
|
|
|
|
|
|
|
余り |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
数字の個数(累計) |
1 |
|
|
|
1 |
1 |
|
100の位の余りが2
![](data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAATIAAACLCAYAAADidBXMAAAAAXNSR0IArs4c6QAAAARnQU1BAACxjwv8YQUAAAAJcEhZcwAAFiUAABYlAUlSJPAAABaxSURBVHhe7d1/aFvnuQfwr1f3ouz6rvJwmFQSFkHDrKwtlreGyNz8UYW0WF4yIpOyyKSjlVuaKutdI9fQ2C3DkddLaqVbaqWstRpIkMIWpK4ZllmDZbguUrgpUkaK1ZEQGZxbmZuAxBqmA/Pue8+RX6dJmp86R9F7rOcDTs57FMKx33Oe854ffr8NTAZCCNGxb/G/CSFEt6iQEUJ0jwoZIUT36q+QXckg2D+IyEdB9G7tQ+QLiX9AxCAh814fBo/GEHyxC33HsvIaIiYJqTfbMXyKN2tJudlfP0ps8nUvi15abOUjLoY2P0uWFtuk9kqJAeaNFRYbc2Hmgo35U9RBIiqd9jO7XEL8Kb6ihupsRJZB6q0g+t5LlVsmSztwZhSJz8tNIoDMp8PyiDmI1ILcWGVBu9xno1PZxQ+JQHIIn5iBmbdqTQeFTML8Zynkirypih3es5OIviCfR2TFS3n5zy5Y15SbKhWRncpgXjkA683lLBJn5nlDHfuuGUwe98DeKDeKBZR7qNVS/kwt6aJ8IjuvyY6kM9rvm7mjIeDZ3fKJRkuVb6fQhUy6otwdKSKx34XIeWWFpPp+ifFRB2wmeaGYQvCdLHwnBuBqWfysUtIV5c8sYo4RJC/Li+XtrgMLcn8oO935GDYdSEIpZYs/CxVarHC0lTsIqXcDyL46joFtxsXPKsX3m+K0H67jOWWFsqouVGXfvBxHqNgNzyO8rQG12yluIVuQv6k9Xdj0SgIFUwcM54bR/aQHoTPqO0KaTSGRmkFhjRVWczNfW6H5BALPr0PXOzkYOs0oTO1G1zODiF/kny9j89MB9Ni6EDhngNNUQOKVLnQPxcsFTZUrOaSmkpj5ygLrY2ao7CFkj8t94tiNRNGMDkMWw8844DmcUX1SFF5V9k0JiQ+y6H7Bxtsa0GI7+b0yYZUyY8zdCuYYSjJ+C1g7mRFmg535T6u/mZz/ZIA5YGXuIzN8TZ34R55NvuFgaHWzcJav00yajbSB2X+dZqp76Ks0G9tpZXjSz5L8YU+90HLfLE37mf+Tpd5IMr+GN/vVbKfAl5Y5xPu70HVIQrvdBeeqcfTYexBSc2P+SgaRt4NIzPJ2ixkWpDA4keErKqC8zuHeBM+pZtg3O+FYCKDDKZ9NtLllJDTpTBA9T3mQarbDscWB0v4OdO1VMyKTkDkaQPCkcvmnMMO8FkjJ/6eKHkLuT33o2hqE9FgHXFtMGH+2Az3yqGLZ03zflJDNGWG6GEbocEj+GkdaXpuOy8ufqtjhtdhOXtCEVCoolT/PwttN8qipvIKVV1XqtJ+ZYGG+OB/bnRuTzwBgrkh+sV2REiuUN0o5O7lZVPmvviqw0j/KHy5vS/2R8jPsjMo9tdRnlUozvwnM8uo4H31fYGObwbA9XP6/K8b7Q3ndxiSP7r7us+Wu2vumViMy9dv5wK9kvKYJp9GgPLpqxMLCSqz+UTtWf8eA8qpKPbweXT+UL8n/t4ji37I4EYyh8ZUwfrtzLQz8n9y7RhjKG/UgFr6/EtYn1qL52wY01sOLLY1L/bGA1d+1Yv0PmvnPolJmrP/J48CXl+T+KSL7x0OIfcuL8G9+jrWVdxDwL4v90fjPf2Ll6vVoX9Wkcjv1onr7pvIE+L/GP8bvotO48sP1WNm8EpaWSjtJ/XbS7BeEEN2rh3EDIWSZo0JGCNE9KmSEEN2jQkYI0T0qZIQQ3VP11PLLL7/kS+RePfzww3ypuqiPKnc/+oj6p3LX9o+qQjY5OYmdO7ah8PcH8dBDBjzA15Pb+973vod0WnknuvpaWx/Bpbn/wcK/NqPpwQa+ltxJNBrFhg0beKt6fvvbEQy/+Qb+3vgQHjLQEXS3Nm3ahCNHjvCWRu+R5Y71oHe2D+Ov21S8WEqq5koKw1tHYT0ShmsVX0cEkkPk2V7kXhnHwI/pCKqEJvfILDuC8M31IfBZncyNojdNdgwcaEdwb0z9zBSkCixwH/Ah3x9Ahg6himh0s98I5x43kr8IqvrlXlJFbV4MmPrg/1M9TiyoAy1O+HYk4X2PjqBKaPfU8pFueKwjiE7RKUVMBjjcXiTfi8oXMkRElm0erNsfRYIOoXum4esX8qhsRw+Gj8ZB53xBtbngXQgidoa3iVjkUZl75zAiE3QE3StN3yMzPOGA93ACSeoHQVnQ3gmEp+jyRUwGtG/0InQySYOBe3SXhSyDgHMYqTsNeY1WdGwLInFa/LGx8qS159jyufVd/NNu9N7F92N7wonMRFofl5ezEXQ/E1keDyjOBND1VuqO02sblckf30sgLfIhpEyE+HwvAseC2P1yBDkBtvXuCplUQH5iEB0rGtDQ8PWX+dkbn4JZYLEBic/FnX2z+EUckbd70bsnsqzmbC/MZxFym6/rn4aGDgzf+CR5zTq4TmaQFf6UP4/Ymz7EeEvvpEt5xPd2YMV1/WNGz/EbyvQaJQIvgcwXvC0cCan9HsQ3DsC3w4vBjVH0CPCA4u4K2fw8pPcvKLPJ8q8SJl/3IPhrF5S8m2tZHnEhcy4v7NDY2OqE+zU/PBv5imVifs6GydJS/8hf58bg+XUQvhvfSypnRSaRXZruW1DSyRDiWMdb+peflzB27pr++WoSA88FEdj+jSMIlu0Z5ObEPIKkKT9c+9rh2bIY0Wfa2A3znnDNH1DcXSFrssG77etswdyxQaS2jt705UpDkxm4XNRwtKNlrmU11TLXUoLF3YeOpZqlvAB7aAUGbvqCsgGGtoy2cWga5lqWydsfOGWHr1NlDNwNaplr2fyEF91X49NyiLyZQtfBbw4ElP4xtsiFT9NIQe32zeypkDxWtsC8FKGozBKMMFKahFxXO9eyxQrr0oZfjGH4rBO+DTd/A9m4Ui5k07lysKpa1ci1rIba51oaYGo18aIlIfNuCKaX3fLudjOLgR4zcxoUnmrkWsoyh8dh2+VQHQN3lQC5lsZWK5bK8vzxYcx0+mBv4iuuY0SzfAglZ7U4grTfN40tN4ySyz/beczk1O1P9znXUkLiUB8sWx38oLkF+XtSvZ9UMddSU6LlWp4PYzDjQNcdwlPLBUilquRang8hatoNp8rQ5GsJlWspJTC614Kuzbc9guRRiQZbV4V909LphduUxIwysJAVM4nyfUxV+9N9z7W8FGWepZSTW1ESdeBnSd5Uqzq5lkoyk9r0pOuJkmuZ3m/jSUG3ovH3rmmu5QUWfn1M/nORknqkOkFpiSC5loWY52ri1K0kh8Ag7+9a0XrfLGXDbOAXIywaH2MjQz7m0ijb8r7lWhZTCYSwDuZvXthfT/789uebu1GFXMtqECrXMoNEJIOONfK1yR1oESKkea7lbBYFedMT5czEEMLT8uXVXBLhw3FkVVyyipNrWUTyZAhYa77JvbHrmRrVH0HV2jcNrW74D/rg6vTA19mMpGkA9jb+YSXud67lhfflM+8dRluFE17NzqKa51pepeWoRKBcy9Ik890xp3MxvVuTdGjNcy2vp9mITJhcS57TedvRVoGN7xJ43zw7yuxKNixPG1euAJzvL42hK6V+O+9pRCZJJWCD8epNy5uRrshn0RajBiMyufIblf/FCOs2PxxryitQXqWC8uQqMTGO5Dn5TD09jrjylETV7QgDjOWNssD+YQ9syg+nSf7+axGbqNx4NZlgvu0PSf43Z2wwaNNBi/2xyo6x7bbyfrHYZ2opT6/iiE4kgXNpJNT2Ee8Po7Ub/ieVRyBLfXa/yT/7rwC78bZHEIqXAXOTJh2k/b75qBODQy6Yi0nE3u1DdFUY0Rdu/ljp7qnfTk3mI7tWal8DvE1ppF+18TVEKBcj6F6dhKcwCuftjidSIykMN3hhyKThU3O5Vmfu8anlneSQywCOR628TYQzO4PYZhusVMTENJtDGg7YWnmb3BVtC1kxi+RHLrRbazFsJ3cjczoO08Z1t3jHjNRa8ax8yba9HevoELonmhYy6XQCwe3dcNB0yoKSz/YTeezebOdtIhYJ6ekgXNscd3yqSa6nYSErIn4sAM8OJ3WCqM7EELzUB2f1MzVIJS4rExp40LOZjqB7pV0hOx9FKDsC7za6+SImCYlIEB1DHtBjGDHlPgph5oAXLg1/q6FeaFTI5hEbCsH2tpcOEkFJnwUwOOuHbwudaIR0MYbBD20IvEBHUCU0KWS5Yz4E18oHyr/THUohKbNJ9M9g9/5b/SI5qa0cInuDWPfO4C1+kZzciepCJn02jL5UD8besGvyEizRmjxafmUEhgMhuJWXiolgJGTe6kNy+xgGbjGjDLkzzV+IJYSQ+03Dp5aEEFIbVMgIIbpHhYwQontUyAghukeFjBCie1TICCG6R4WMEKJ7VMgIIbqng0Kml4DeOqZ1QC/RWC3Do+8PoQuZXgJ661aVAnqJdmofHn1/iFvI9BLQW8eqEtBLtCNaeHQVCf+7ltKZEDw7ejHvTiL6hv22CU6kBhbmkRjqwabjJoQ/CsNNc80LZ/7kIHqeisF0JIrwzuWZpyHwpaVOAnrrmOYBvURbQoVHV5fQIzKpKMFgLCLyjA25/jwGHi2iKI/JahJJSL5J4v1xZhgNh6zIH3HBWO4z6iAxSCgWAaMxg+GGUVjzYbiaipAMNcpdraIHfiXjy8JpLP+0G7GwsBKrf9SO1d8xLLsO0LXGpf5YwOrvWrH+B80wUAcJpJH3x4NY+P5KWJ9Yi+ZvG9C4DF+6ovnICCG6twxrMyGk3lAhI4ToHhUyQojuUSEjhOgeFTJCiO5RISOE6F5NX794+umn+ZJ2/vznP/MlolZ/fz/+8pe/8JY2fvazn+G5557jLaJGLpfDSy+9xFva0eMxVNNC9sknn/Al7Tz11FN8iahVjf5RUB9pQylk586d4y3t6LF/6IVYQoju0T0yQojuUSEjhOgeFTJCiO5RISOE6J7YhexyCsF9QcQ/GkbP1j5EvtBumuvcsR70HKMpANWRkD0eQOBoDKE9Xeh5OwVNM2JmI+h+JkITNaogfRFD4J0IYof70OUOIKXM26+WMmHj870IHAti98sR5ESYfV55aimmPAvv8rNkabFVOOFlJpOXjV9abFeqkB1n4f0e5jCBuSJ5vpZUopTyM+/Vn2GajWwAsx9I87ZaeRbdaWLYHpaXSEVKSebf9fXPL33AzrBhRO4pNUos+YaNOT+8UG7lIy4N+7xy4o7Izo8jtGCCiUdYGTe70DMfRGgit7iiQsZWJ9yv+eHZyFeQCklIxhIwmpZmg7XB9bwDqT1RpPgaNaSTIcSxjrdIJaTpKBItJlztoS0eOE71IfopX1EBacoP1752eLZYym3Txm6Y94SRqPGoTNxCJkkofTCIwDS/WDGsQLP8V2yWLjTEIMldNIPhvWFk+ZoVTUo0TBY5tSk9V1IInLLD10lRM2pICxJm9g0ivJRzIR9D5R6aq/wYyp4KyZf6Fphb+ApllmCEkapxloa4hexRL5Isj9GlnblYQF7+y9u2PFNg9McI58E8WMqLpR7Jz8uj5bYOWFfxFRXKHB6HbZejfOIilTN2jiLPkvA+yldcziMnj5w7rCa+4t4ZW24YJZezZucxk6vtAEM3Ty2LUzEEN4zIQ1o6S4spg8SRPLxDHvlQUeF8CFHTbjiXzvhEM5mTYeR3+eFp4ysqYOn0wm1KYkYJzJYVMwnE5L/LQc01pI9CdiUB/7sWJCd86g4SUjW5D/xI70liVNWJJofIh4Bne+UjBnIL8gnCf7YPyYNOddmwq1wITfUgdzCA2EQIoc+NcMmr2y217TPxC1kxheEXU+iODcBOgzEh5Y71YtgwgvDOxRvAFZvNomAGEoflA0T+Ck/ngbkkwofjyJaj/0lFZiPo3b8CIx+6YdEg5MrQ6ob/oA+uTg98nc1ImuRjU8UoTxP86aWYcuPMPxRlF/7B23NhNnBk8bGvOnkW3k6vX6hXYulDA2z0dIG3GUsO+VmSL6ulPNqn1y/UKWVG2cChNLvaQyk/80/z5UqcHWV2WJjvk8X3otL7bcz5vhbHpDriFrK5KPM8AmVmjmu+TMx/mn9eodJcmk3Gx5i3Dcy2a4yNJ9Isz99VI/dCLmL7HUy+oLi+j3ZGNSg8BTaTGGejyntkbT4Wpj6qSOn0SPl9yev6B24WVdVBF9j4kI+N/GGSRQ/62EBkRt4Tao+m8SGE6J5unloSQsitUCEjhOgeFTJCiO5RISOE6B4VMkKI7lEhI4ToHhUyQojuUSEjhOgeFTJCiO5RISOE6B4VMkKI7lEhI4ToHhUyQojuiV3IKNdScFXMtZyNoOdZyrRUqyq5lrNxBN6OIK5MP//ybgTPCBBsWZ7MR0iUaym6quRaXpph45ER5nmSMi1Vq0qu5Qwb3Tkq/7lEbncOsMkaT0om7oiMci0FV6VcyxYrnDt88L/QwVeQSlUj1xIXM0iczCF/depxA5oNRSVMqabELWSUaym4KuZaEk1UI9cSqxzo3hjAps27Efm8iOKpCMbtcoGscZ6GuIWMci0FV71cS6KNauRaAia4P0xjpDmInsea0XzQgsBrtqujvlrRzVNLyrUUnUa5lqRqtMi1VOQmgsjuSCMd8cEx1QPbsxG5QNaWPgoZ5VoKT5tcS1I1WuVafh5E72k3RnfaYNsxgslUFN1nfQhN1fYmmfiFjHIthadZriWpDg1zLefPJmC0rfv6UnKNC749Hchd1uzFm4qIXchm4xh+Nw/3EV7ELkYweLTWg1jyNQmZ9wYRXzuCMV7EUvuG1T21JJqSzgQxOGHFyPu8iJ0axrCKp5amxxzIn0xe876ghFy2Gd32GqfD89cwxEO5loKrUq5lKc/SiXE2tsvG0OZlY/FJlp6jDqpEdXItGStMjzDfa2MsmoiysSE/G8vUvn8o15IQonu6eWpJCCG3QoWMEKJ7VMgIIbpHhYwQontUyAghulfTp5YnTpzgS2LbunUrX6oveumfhoYGbNmyhbfqRy6Xw9mzZ3lLbNU+hmpayH7605/yJbF9/PHHfKm+9Pf3469//Stviau3t7duC9kvf/lL3hJbtY8heo+MEKJ7dI+MEKJ7VMgIIbpHhYwQontUyAghukeFjBCie/VXyC6nEHhlEJGJOCJ7dyPwaW0nhCM3UuY468Pg0RiCL3ah71hWXkPEIyG1rwPDp3iz1pTXL+rHBTbWaWMjGd5UshjbnGzsHG+SmislBpg3VlhszIWZCzbmT9F8ZOIosfzpKBt9zcWscvnwp/jqGquvEdn5hDwSc8DWytuwwrZZHplN0ayzosh8OoxgfxApJc90lQXtyGB0ailwjtSeAaYfu+Dd34cevkYEdVXIpFwWCTRjxdUJxw1Y8W9A4lyOLl8EYd81g8njHtiVaZl5BGBXK2UBkNurq0JWvHyLkdfs/DVzkJOaarHC0abM/15E6t0Asq+OY2Abpc6Q26OnlkQ8V3JITSUx85UF1sfM5YR5Qm6nrgqZocnMl27QYqx5UjK5RpMF9ied8Oz3wnKwHc63MnTpT26rrgqZ0WqDA3kUrl5HFlHIA7a1ZnWhpUQjEjJHAwieXLoFYIZ5LZDaG0eGryHkZurr0vIRB9ydSWRneRs5ZFNOeLdQfrkYsoj39yEwkeX3LEsoKQvbLaDb/eR2HviVjC/XgWa0P70WU/8ZwsVGCf/9wREUX/od/uMJurAUgxnrf/I48OUlFP9WRPaPhxD7lhfh3/wca6mLhFH8IoHk9DT+8PsE5r7/OMz/Jx9ZlpU1vT1D85ERQnSPnloSQnSPChkhRPeokBFCdA74f6GAoEy5CGEEAAAAAElFTkSuQmCC)
|
|
|
|
|
|
|
|
余り |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
数字の個数(累計) |
2 |
1 |
|
1 |
1 |
1 |
|
100の位の余りが4
![](data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAATUAAACTCAYAAADvLY5DAAAAAXNSR0IArs4c6QAAAARnQU1BAACxjwv8YQUAAAAJcEhZcwAAFiUAABYlAUlSJPAAABdYSURBVHhe7d1/bJP3nQfwN7d0Mr3c5ExwsldYsQRaHIFUZ6WqreUPXLFTHIGE0zDhiE7gdFJr1u5wFqnERRN12huN6Qq4aG3c6EB2TmU2OlAcqVWM1kx27+DiaKCYE4gnE+jsE0i2RHR5dMvuueexv6HAoICfx+Sbx5+XlPB8HyPLyfd5Ps/3+ZHve5kkAyGE6MTfsH8JIUQXqKgRQnSFihohRFeoqBFCdIWKGiFEV+qiqInXs8jOiJXGvIjscAzZSovwYl5AYl8PAnLfhN4IITPL1hMOZBFyDSDDdiHe1UVRK00E0WpZjmXLlsFs24NJuxs29hrhgYDY7peQ3nQUwV0e+LYXETlTYK+RRScWkR8LwLF8WXkfWvgyv5IAj71UJ6efrRjKFVEsziF/YQjeZgNbT3hQOhOC/2Y/fJuVfskhsn8A0zeLlRfJ4isUIH58FcojrZWvOYy/5UX4XTdM7L/whNOiJqJwPgOhxJoaWN5ohNGodTErIXc2i8I8a9aTmzmkprQ4TheQPBEG2lphKbet8KUkpH9uLbfUUi49ZK5ouCEtGRpum402+LZVekchjASQ2XoU7lVshSra70PcFTVxVjlxLyF10I3YFWWFKJc4tfKIHw4hNpZAaHcPwlPq31EsX/PJIeEcRPqmvFj+3HVgXu4PZQO8ksBLh9Ll04/K76JaAqZPAi3XkgifSCL5SS963s/IW4BKbLtRLj24TwrKCmVVXdB821xhhXUFW76ewMAFF/wvqh8g1Gof4quozcs/4N4OvPRGCkWTA4bLA+jc5EVEZREytvkwuN8PT7sb/gNOpNp7kVR+idUqpOTi2IKODwQY2s0ont2Dju0BJK+z13WsMBFCt60DocsGuExFpN7oQOeBZPXXVq4L8mYNTBvt8O50wfVqAK6cA64P1N3KyZ2U+8S5B6mSGQ5DDgPbnfAOZzU4QHKuptumiNRHvbBsdUJ1Savl51T+9pM3c9khydMMyXkgLRXZOu2kpaD8Y3s+y7N29fKf90tOWCXP8Wm2pk78OS+Nv+2U0OyRojm2rlrFUckn94c79nV/pA9AgikoTbJ21W5NSkM7rRI2BaX0DbauTtRk27wRl7zwSHH1u85ttficnJ1+Ckj2daDjIxGtdjdcq0bRbe9G5CJ7uRoXw3AscyB8z3ssb1BxrJnNIux5Cd6vmmDf7IJzPgSHSz7K1MENO3EqjO4fe5FpssO5xYm5gw507FMxUjNaYdvMlu9kUjcWEM70omNrGOIGB9xbTBh9xYHuT5Qxoc7VcNssZVKIoAVmLe4O1HIfYsWNG3PFOfl7Xop2maTgufIKqbyqWjfkkUDXkHSVNaXcUclp8kmjqo7cc1Kx/KGUUR87ct0qSnN/Lr+obwv9kQlK2BmXe2qhz6qXj7klkzwqryhK8V2QXB/f7rHqsP4ov/e7yphvoc/0rnbb5tWP5dE55FEva6tTu8/5rV/JWH3jQoOhQfmO+fmVWP3DVqz+jgHlVdV6eh2c6zL49aFzmJ09h/AJAT/5599g6/fY61VpgKH8oZ7C/LMrYd24Dk1PG9BQDw/IyCPcSn/MY/V3rXjhB03sd1G9xg3/gJf++GuE/tiA2S8/RPKZCH77mlXddZtvV/qj4S9/wcrVL6B1VaPqz7k01G7bLKR/i3DxBfh7XsBKtq56tfucNJ8aIURX6mFsQQipI1TUCCG6QkWNEKIrVNQIIbpCRY0QoitU1AghuvLYj3SMj4/j2LFjrEUex+9+9zu2VFsvv/wyWyKPo7e3Fy+++CJr1c6HH36IiYkJ1iKP6umnn8bx48dZ68GqKmo3/iOC3/zegp/ubsXfs/Xk4To7O9lSbcXjEfxb+BP8d8cvsHXNU2wteZhnnnnmiRS1ePxfICR+g/Hv/xQ9z9Me9DgeZR+q+uFbYaQbPTO9GH3Lpv4v9on2ZjMY2HoU1uNRjea9ItoSEHulB8Ibo+h/nvYgLVV9Tc2yIwz/tV6EztfJJFVLTaMd/YdaEd7H55TLxALPIT/yfSFkaRfSlIobBUa49nqQ/nmYQkx49ZwP/aZeBM/U48yvS8AKF/w70vAdoz1IS+rufq7thNc6iPhZOtTwyQCnx4f0sbh8skN4ZNnmRcvBOFK0C2lG5SMd8mhtRzcGTiTVT79MauM5N3zzYSSmWJvwRR6teXYOIDZGe5BWvqGoPVrWn2GjE77hFNJLoE+UmxvdI/q5wlQ6swc9D/15LGhtB6Jnl8gpzkwMndtj+rgOOBVCx3uZh0whbkBrmw+RL9J8DwyUSR139yA0Esae12MQOB5ZPrioPWrWn9EKx7YwUuf4/SlLl5KIvd+Dnr0xXc1RXyzkEPGY7+qfZcscGLjn5o1towvZscklcApaQGK/HwnWWurEG3kk9zmw/K7+MaP75N0l26jMznsshUluN04RmYNeJNv64d/hQ6Atjm6OrwM+uKg9ctafBRYbkLrI71TJxmZ5iP/LILxtbIVOFK7ZMD630D/y1+UheN8Nw3/vIwJrWuD+Iosc56Np8YsIkmhhraUvXxAxdPmO/rk1jv5dYYS67pkPe408mkYK2UuszRnxbBDud1rh3VKJyTO1dcK8N8rtdcAHF7XHyPqzrHUjezmv4fBZ+9zP2ljM3E8RFk8vHAv1S3ku7aPl6L/fc4OrlJ0mjdwMa2tBs9xPRv78oa/s8Lcb2QptLGbuZ9NGHzrXsobyXNr+DDoO3y8AWB4YdGUhXNPyc2q3bea+ishjaAvMCzF5yuzHiCKjJjvktieZ+/kYWX+GRrO8kZc0ObWrTe6n9hY/99MAU7OJFTAR2SMRmF73yJve/cgb4XNZbXIvNc/9rMgOj8L2mhNNrK0aB7mfxmYrFkp04eQAptv9sDeyFXcxwCjva3mNtiGtt03jintGz+XfbQHTgrqD2iLmfj4868+4Ui5qEwLyrF21GuV+ao633M8rUQSyTnTcHhXcywzzOmD6mvqRlea5n4orEcRNe+BaOIhqgKvcTzGFo/ss6Nj8wD0ITfIulJ5RvQfVZNu0tPvgMaUxrQwyZKVsqnzds3xwq9ai5n4+StafkiykWcqMVKPcTyWh6u58SbV4yf2cPGhjiUkPovHPrmXup3RVir71ddqXkv6Ermg5pUo1TnI/iwnv7eStBylnnd5O1FJP621zLheV+n8+KMWTQ9LgAb/klktHMMNeVGFRcj81zfp7qBrkftYCV7mfWaRiWTjWyIf6J0Dz3M+ZHIryR08NRxCRv6IT8mjlWhrR4SRyKk5r+cn9LCH9RQRYZ77PtbQaqNG2aWj2IHjYD3e7F/72JqRN/bA/x16sxmLmfj5S1p8yUtMiUVumee7nbVqOVjjK/Zwbl/z3JJz/tcrPrkUqfS1yP++k2UiNm9zPq9LQ5oePwpSR2jePth9VDbbNC0clOyyS//PK7085M1Cdy1rDfeihIzVRnANeNN6+4Hk/pRvy0bXNAi3GCgajct3BCOu2IJxryitQXqWCcgcsNTaK9GX5CD4xiqRyt0XVxRUDjOUPZYH9027YlF9Oo1FdPmm1lIu2JhPM3/hLyiMv/+wtqzUYKyz0xyo7hrps5e2i0mdqKXfBkoiPpYHLk0ip7SPWH0ZrJ4KblNsnC332pMn9cwuwG79xD0JR3oW0GW3XYNtc70LggBvmUhqJI72Ir4oi/ur9b0k9utrtQ1VPPXSnwkgnzBNeFD9yfWPxI4slg4FlPhiyk/CrOWUgNVJAbLsZ6Z1FHN1Ce5Baj3D38+GEKwnY1pmpoPHquoBJOGBVRr6EQwKEkzZYVtMepAUNiprcIVnAud7K2oQ7M9NIbLbBSvsMn2aUg44TtmbWJqqoL2qlHNKn3Gi1Lsb1CvIosueSMLW1PODBXLLYShfSSHS1ooV2IU2oLmriuRTCXZ1w0pTRnJJHAWN57NlsZ23CFxGTE2G4tzmfzCMfdUBlUSshORKCd4eLOoRXUwmEb/TCVfs8EVKNm8oMMl50b6Y9SCvqitqVOCK5Qfi20cUaPolIxcJwHPDCxtYQvginIpg+5INbwz8Rq3cqiloBiQMR2N730Q7DKfF8CIGZIPz0mACfricQ+NSG0Ku0B2mp6qImjPgRXifvND+iq5tcUqby6ZvGnoMPmrmDLC4BsX1htHwQeMDMHaRaVRU18fwAejPdGHrb/sCZO8hikkfRbwzCcCgCDz2bxiER2fd6ke4aQv8DpvMi1dPkLwoIIYQXKu9+EkIIX6ioEUJ0hYoaIURXqKgRQnSFihohRFeoqBFCdIWKGiFEV6ioEUJ0hdOitlQS2uuY1gntRGPaJ58vFdwVtaWS0F63apTQTrRTq+TzpYKvorZUEtrrWE0S2ol2apl8vkRw+bef4lQE3h09KHjSiL9tp0AX3swXkDrQjZdOmhA9FYWH5tbnTuGLALp/nIDpeBzRnfWVH8LZ6ecSSWivY5ontBNt1TL5fIngbqQmlkQYjCXEttsg9OXRv76EkjxWW5QcWvLXRNYfUwNY9pEV+eNuGMt9Rh3EBxGlEmA0ZjGw7Cis+SjcjSWIhkUK214E3/qVjC1zoaH8m2/A/PxKrP5hK1Z/x1A3nbEkNCz0xzxWf9eKF37QBAN1EEcaWH88hflnV8K6cR2anjagoY4e3qL51AghulJH9ZsQUg+oqBFCdIWKGiFEV6ioEUJ0hYoaIURXnvjdzzNnzrAl7WzZsoUtEbVq0T8K6iNtCIKAixe1fxpdT/3zxIva1q1b2ZJ2Tp8+zZaIWn19fbh06RJraWPbtm3YtWsXaxE1lKL25ptvspZ29LQP0XNqhBBdoWtqhBBdoaJGCNEVKmqEEF2hokYI0RUqaoQQXeG6qAknOtE5ot3sdsJIN7o1fL+6N5tBwDaADGtqYiaGzu0xmnRSEyIy+1sx8BVrqqFMPrm7B6GRMPa8HoPA8Qz7/Ba16wkE+hKsoU7pUhKx93vQszdGIS6aEZE94sfAFGtqooDEfj+06XUing/B/06WtdSQi+NBL5Jt/fDv8CHQFkf3MS3etzY4LWoiUieSwAbWVMnY7ILnl0F429gKot6VKOI5M2toQ/wigiRaWIuoIyB6ehpa9JB4Ngj3O63wbrGU26a2Tpj3RpHidITAZVET/xBC5nk/OihxhVMCYp8C3p+1srYG5FPZ0Fd2+Nup07UgnIgAr+yBFj2U+yoij6EtMK9gK5TZjxFFhtPsEA6LWhaRpA2+zU2sTXhTOhNBcbsXFg1n8c4Oj8L2mhPU6xq4mUSk1AnvWtZWybjintFzOYu3gGmBzyuf3BU1YTgO8+suisXj1WwK4UvyDvMca2vhSgRx0x64FkYCRAURqU9y6HzVxtrqWdp98JjSmFbCxWWlbKp83bMcas0hvoraTAyReS/cq1ibcEZE5oMM7K/Z5NMPrbBT2S4TaxM1KpdufLBpGe61yo3I2W4Ih0NIjEUQuWiEW17dauGzz7hKkxIyX6LwP9dwYSqL7NQ5nDv7OS7/rxn4vya0/GAl1J3tzOLCyRBy1l78ZEMjW0cey+wFTFy6hRtXlP6Rv859idNf5mF6dhbLVyrJX+z/PY6ZDL78r1lcm6685zl5G/j8P+dh/hbQtG4dVn6b/T/yCERc+H0Ot0q5Sv9M/Tu+/NcJ5L+3GrNPfQ+t369+u29YsQHOdges61rh+Ntz+MUZO978J6emlyA0o8zSwae8FO2C5I7lWVstrd+PSJmgBASlNGtqIR9zS+iKyr1F1EtLQXkXD2ZYs1oXjkp2WCT/53Pl5uRBm+T6+Gp5mUd8PtJxM4fUWByjE/LoTT5/T50vyMeg6onXs/L7jSJ9WX6/iVEkz2ZRoAfWVBBROJ9C7PSovDyJ9FgKuZuVV6pXQu5sEvGxNHB5EinqI1XK2/zIKMo9lEkidalUeaEa610IHHDDXEojcaQX8VVRxF+tPN7BI5pPjRCiK3yO1AghpEpU1AghukJFjRCiK1TUCCG6QkWNEKIrVNQIIbpCRY0QoitU1AghukJFjRCiK1TUCCG6QkWNEKIrVNQIIbrCX1FTorj6AoidCqNnay9il9RP1aDMWJCdYe8zLyI7HAO/WThLiGYReSVkjgwgfCaBAU8HekdyqmZlIQvqMyKPs/nU5qTxt3xS/EalVZ5b67mglK5M41S18vvIP6ryZVrvlYZyKt+QyOakyXftmsynlo/5pGCG9cmNUclnMkm+08VKm1Rt7lxQsmsxn5rc1+m3bZLr08ocasr+ZD80WV7mEWcjtSwy74XRe6xy7DdZWoGpo0ipTq1pxVCuiGJxDvkLQ/A2aznXcZ3SLCJPwOiwCNPCzNArnHDvLCA8nJRfIdWjiDxO2OG7MI74q/LxRVa6kZe/d8C6ptxUZXmjEUYjFTNtaBmRJ0K8FUHgUEo+CVUYsPzv5H9OCZTSrgJF5HHEuN4Jm3LULmUQ/iAH/+l+uFWnDOURPxxCbCyB0O4ehKfoio0a2kbkWeHLSMgfXkgQK6GoHMtes8mvkKpQRB5/xJkMUplpFNdYYTWrT4I0tvkwuN8PT7sb/gNOpNp7kVQ9/XSdqkVE3p1uppA4ZsfgzygmsToUkcdlUTOsscPZ7sXgGxaEN7owcF7dyMqwygrLQpDOKgtaC2FEz9LJzeOrRUTeneQd8mAYlokk/LUqmjpHEXm8FbXZLGLvh5GaYe0VZvlMPoPAmIoHMC6G4VjmQPie8//lDXR97bHN5iAYTRBOyhv2sPyVnJRXTmJUXs5cr/yX6pWQec+LzNY4+n9EY7TqiMgJRpiuRyv9Mzwq947cQ0l5+Q/qDuKGZg+Ch/1wy4MNf3sT0qZ+2Hk98LC7oHw4F5RMShRXkt3OvzwkOeWPqCrWTnlEoGtIuh3olTsqOU0+aZQ9NkJU0Cwi76o0eiAoxQXWVOIM345+3WekSvUZkcdZmpR8pDkZRrJkgXUtkDsRhdAWQHCXTdX1FXEqjEAMcNiB1JgA575BuDW4o1q/lIi8NFKJALrfM2Mw6YNroxPWqm7oFJDY7UDn8N0PcJjenUT+Le2uC9Ub5YHz9EQcAc8AzIdG4Wt3wNlc7V4kIPlOGLlmFyyFJCZXeBHYYa3RJQj1KCKPEKIrXN4oIISQalFRI4ToChU1QoiuUFEjhOgKFTVCiK5QUSOE6MoTf6RjzZql8YDYzMzCnzXUl76+Pnz22Wesxa8jR45gy5YtrFU/BEHApk2bWItfLS0tSCaTrPVkPfGi9qc//Ykt8e3ZZ59lS/VlqfSPoh77iPrn4ejhW0KIrtA1NUKIrlBRI4ToChU1QoiuUFEjhOhK/dwomEkg8O4kLJuakC04MPiPdm6nTqk/Su5nGJNrrCiNRFDcMoggx1Pb1CPxUgzBj/Jo3WaBcGoS5tcD8PCayqYUNd0TopJnrV8av6U0lAxDrxS9Vn6FcIByPzk3Ny71m7y383ilG3HJa+qXxjmNz62D088Skgf9KO3zwankFFyKIPDONIqVPDay6Cj3k3fiRBIDG+ywLUwCusIG+4YBJCf4TGXTf1G7nkTkGODYUAliRbMP41IavvWVJllslPvJu/xMFjAux3LWhry03AhkZ5QsQ/7ov6jNTCOBFuTHwoiNyQVubw9Cf6BhGj8o95N3hUKKLd0tVaDcz0VRuJaTv0/D+CMvPO0uePe5kGtzITRVeZ1whnI/iUq6L2qGRrP83YGWdexODYvdG1QTu0dqhHI/eWRovH8Ajq2Rz7ufui9qRqsNTrZ8JzM9L8AZyv3klXW9vAddzuPrK2jy8mV5qLCWXafmjP6vqa3tgLcrDWEhbPdmHgJc8G2h+DV+VCLY8juirKAVENsfo7ufnDC0udBfyEG4yVbcFJAr9MO9mc+DT308fFvKItwXhWGbA6VTSRh+Ngjf8zQa4APlfi4FovIo1KESHDssEE6kYOwbhJfTh2/r5y8KCCF1Qf+nn4SQukJFjRCiK1TUCCG6QkWNEKIrVNQIIbpCRY0QoitU1AghukJFjRCiK1TUCCE6Avw/eXoVyA1DqS8AAAAASUVORK5CYII=)
|
|
|
|
|
|
|
|
余り |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
数字の個数(累計) |
3 |
1 |
1 |
1 |
1 |
1 |
1 |
ここまでくるとだいたい何をやってるか分かってきましたね。
最後のループで一の位を確定します。
# for i in range(N):
i = 2
for j in range(B):
for k in c:
nex = (10 * j + k) % B
dp[i+1][nex] += dp[i][j]
dp[i+1][nex] %= mod
pp(dp)
やることは同じで、10の位の余りが0~6のパターンで一の位(右から1桁目)が1, 4, 9の場合の余りを求めます。
10の位の余りが0
これはループの1回目と同様ですが、右から2桁目までにこのパターンになる数が3つあることがすでに分かっています。
従って一の位については、最終的に余りが[1, 2, 4]になる数がそれぞれ3つずつあることになります。
|
|
|
|
|
|
|
|
余り |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
数字の個数(累計) |
|
3 |
3 |
|
3 |
|
|
10の位の余りが1
|
|
|
|
|
|
|
|
余り |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
数字の個数(累計) |
1 |
3 |
3 |
|
4 |
1 |
|
10の位の余りが2
|
|
|
|
|
|
|
|
余り |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
数字の個数(累計) |
2 |
4 |
3 |
1 |
4 |
1 |
|
…ということを繰り返して、最終的にdp[N][0]
が、7の倍数になる数字の個数ということになります。
dp[N][0]
桁DP、完全に理解した!
解説②
桁DPの基本的な実装ができても、小課題2,3は未だACできていません。
そこで2つ目の解説を見てみます。
kyopro_educational_90/005-02.jpg at main · E869120/kyopro_educational_90
想定コード
kyopro_educational_90/005-02.cpp at main · E869120/kyopro_educational_90
Pythonで書き直したのが以下です。
mod = 1_000_000_007
def mat_mul(a, b):
m = [[0]*len(a) for _ in range(len(b[0]))]
*b, = zip(*b)
for i, r in enumerate(m):
for j in range(len(r)):
r[j] = sum([x * y % mod for x, y in zip(a[i], b[j])])
r[j] %= mod
return m
def mat_pow(a, n):
ret = [[0]*len(a) for _ in range(len(a))]
for i in range(len(a)):
ret[i][i] = 1
while n:
if n & 1:
ret = mat_mul(ret, a)
a = mat_mul(a, a)
n >>= 1
return ret
def kaisetsu2(N, B, K, c):
A = [[0]*B for _ in range(B)]
for i in range(B):
for j in c:
nex = (i*10 + j) % B
A[i][nex] += 1
return mat_pow(A, N)[0][0]
# 5は終わらない
test_all(kaisetsu2, 4)
結果
Subtask2が AC になった!
提出 #32514921 - 競プロ典型 90 問
![](data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAASwAAACCCAYAAAD8HPVfAAAAAXNSR0IArs4c6QAAAARnQU1BAACxjwv8YQUAAAAJcEhZcwAAFiUAABYlAUlSJPAAABzcSURBVHhe7Z17kBTVvccPBETeKMpTHonmhjcKaspHSOlylbJWuIVSsVJQUmKMFV9EQxUlioqRUNFEfKWMiNGC0lulUC5ahhtF/xA0RoQgzyggYJCHovLaBdmwdz9n+zecaXpmemZ6drt3fp+q3pk+/Tq/Pr/zPb9zprdPi7p6jKIoSgJo6X0qiqLEHhUsRVESgwqWoiiJQQVLUZTEoIKlKEpiKAvBWrJkibn66qvNZ5995qU0wDrp99xzjzly5IiXqihKXEkTrEwVG9j2xBNP2E+WpuDbb781kydPtvnww7Y77rjDrFq1ygoQ65K+ePFic8UVV5jvf//7Ni0Xcp3zzz8/58J+ci1FUUpLmmBdcMEF5oEHHjATJkw4qSKOGjXKbN682Zx11llm2bJlgaLWGMydO9fs2bPHioUrnF26dDEVFRVmxYoV5sILLzQLFiyw4jV69Gi7fdKkSVboEDMRI+zctWuXWbp0qbn00kttmiuGY8aMMcuXLzcrV640M2fOtGnPPPOMXX/rrbfMkCFDbJqiKI1DxgdHqew33XSTuf76681tt93mpQYj+1KZR4wY4aWWFrpwv/3tb82aNWvM448/Hhg9bdiwwfz+97+33xHcP/3pT2batGnmyiuvtAKH6N5+++1m+PDhVshOPfVUuy9CPXXqVLNu3Tq7ng1ECxHlfIqilBYbYVH5qbDuWA7CQ3RBNBPUBXM57bTTTM+ePc2///1vK17SXXIX99wuREls5zhBxpbc68p5ZT/EBcEiIkR0giK+QYMGmfvuu8/s27fPihVR0s9+9rPQ4qIRlqLEi1SXcMqUKVZw6BqJuIgouBGWCAdCI8IiXatZs2bZSIvKTaVmIUKD8ePHpyIYhEjGyhhbQhiIkqQL+s0339jz9evXz64Dgsh5Ob8rXAjra6+9loqwRHz9XVrJB+ls5xxBXUJXOBVFiRl0CV1qamrqZsyYUTdy5Mi6jz76yEttoF5I6uorvt3Ofi71gmO3sY9QVVVlz8M2l61bt9ZVVlamzsN12I/9QY7zX1+Q/YPy4R4r3/1LpvMKYmfQsf7Fb7OiKKXjJMESRFTcyo3wkMY2P4iDu03EIkhUwBUWEUkqf33Ek/qeSwjIj3t+ybNfIEXgxBa2i+C4SybbwM2voihNQ0bB8iMVls8gRBTYLgKUSaxAxMW/j3uefJCoyBU6V8A4J59snz9//kniwzYRrEyClmlhf0VRSk+oB0cZc2J8ijGksWPHeqnpyMD79u3bU2NfLDJu5YcxJ8ae3H0Yc6qv/HYwm1/1wsJYGI8tgPuLXb1w2c8zzzwz9Vlvs9m7d69dzwRjdjIGJ4PtLtj58ssvp/bJ9SuqoijRkFWwZID9b3/7m62gmcQKqMQ8HsCvikG/BuZCRIdf9PhlL8wveTLAzuA5g/fPP/982nH8iNC1a1dzxhln2HU+W7RoYb744gu7ngsR6vqoLCVcjz32mLWTa+oAvaI0LicJlogAQiW/+Lm/wmWCKKl79+5WJPIRLPeXRoQAYcx1LRFSftnjejxiEBTlEO3Vd9nM6aefbtf5RNTkYVL5xZHlhRdesGkgeSKNxxjcc7dt29ZGhYgYx+d65ENRlAhp6BmeGDtiyTb2lI18BqZlfCnsGJCMi0kew1xDENvkmKB8yhjWu+++az/9Y2hBx0ieZOxLUZTSkvFJd0VRlLgRatBdURQlDqhgKYqSGFSwFEVJDCpYiqIkBhUsRVESgwqWoiiJQQVLUZTEoIKlKEpisA+O1tTUmP3795vq6movWVEUpWk45ZRT7P/88q90/CucixWszz//3L7JoGXL8gu4+F9EJtZojjRn24RysBHKxU7h+PHj5ssvvzR9+vTxUhqwCnXs2LGyFCtFUeIJeoQu+VGVUhQlMahgKYqSGFSwFEVJDCpYiqIkBhUsRVESgwqWoiiJoWDBev31180vfvGLtNmVi4VzcU6mlQ8D+zGj9LZt27yU5gF2hb0HjUXU5b169epYll3UdpainkRF1GUg9RebS0ViIywq9MKFC83u3bvNz3/+c3PxxRfbpZQ3C7iuXOv+++8vaIaguICj4rBiDw6cL9jPfSjk2GxQjoXmyU9c7RQbWaLyJRENOW+h9QE/j7Iucd8kT8WIZNGCxQwzrjMEZShIeQuNIsT5mCnnxRdfNO+995554403zODBg+1UXzIjTikg/9x4rvf222/btI0bN9rPpEGZPPTQQ+aGG26w9/Cpp54yVVVVeVca9t+5c6e3Fg34xezZs7214oirnfjRc889Z30Yf+Lc+HQxkEfm5TzvvPOsrZz7nXfesfcgHzhPrrk784E6++CDD9p7T76oo8xelW8ZQF6CxQVoCRAlHGr9+vW28EU4+OzRo4cZNmyY/aSCI1Qwbtw4uy83T25I37597TY/RE5cw9/qUMhEU0RVLGI014WpU6dmnLg1Cnbs2GF69+5tr8FC/nAO7BSxljyTduONN6bEnOnL5N7xyf9u8vnII4+k9gkScBF7tvsbgmLgvMwBiT2AHeSHSiM2yLXdqIIKQV5I535MmzbN+sEtt9xi8+/ml0WOZZs/TZBGiOt+8MEHdvtLL71kG6FiiZOdrJPOPszjuXjxYtO/f3/rS+SP6xQDtiB8Uq849x/+8AcbVJBX8sw+2O0GD6+88orNF2Xwr3/9y8yZM8fORUodZ1/xVbFLjnX93j0fyHU458GDB20d5d4L3bp1K6iu5iVYUkkRp4kTJ1qHEpEggwgITJ482aYxbyBww9zviM3HH3+cciI/nJtrIHKXX3556mZLyyHiyDnYjiM8/PDDoSZfLYaLLrrIFqSbJxYmayVP/qiLf+CkFaVlefTRR6090ppu2rTJ7nPo0CFrC/tQiVxB4p5ScTiO8997770Ft0x+pGGhAgY5XBBUWLEBuP8zZsyw5yL/v/rVr6ztlAX5lWhGRIjjSHdhdm6JgPCtH//4x2bevHmmc+fO3h7FERc78XuJMjiecwlSH/CvYsD/qSMIDbYijLng2gMGDLC+y31atmyZrdPU7bvvvtuWya5du2ydxiZ8laht7dq15tVXX7XrpJ9zzjnm6NGj3lmN9Xtg+9ChQ60eSMNEsEJ5F0JkY1hkkMpMRlB2kBtIYZJh+f7hhx/aSp5rwlQRKAr4qquuOqnFEnAwtmdS+6iQ/CCoXBNbESxaSwoCIeMeSNdBojGm8R80aJD9ZJ10mX2aSVxJ415wT2R6fRBHFgek0nHuKASLa+KMOBSVh2vkcnCcmHxKuTJNv+ukQKXjnG5+27VrZ6Mc7hdOy7GAfezD/ShVVz4Odkpkho2SJuA/CHbQtkKgriCY2EBPBdu/++47b+vJcE+GDBli7xO+SB07cOCAt7UBBG3dunXWVno4iC/QILPOMezTpk0bm849pvGVwEVAF4gqia6I4grx40gEi5tOplHkyspKL7UBhIT/NMc5uZmoN5WaFixsRERBIhR8YiSFwI2iRaBlYBuLFFSpEadAYGhp77zzTuuk5IVxtGIQsRN4xQYVQ2wk+gh738IgTkTZ0fIF/cNpJnA8cVIBMZAog2gC+I97rkGESLmJYFBZmEUbUS52/CYXTWknPomdCAjHCNQbupr4NT4VFfgHfkK+8KdsguWHxsNvKwGAjLex4JMdO3a012CdyJE6KaL+61//2tbNTL0BxL7QhjcSwZIb5BcrwFGeffZZ+0kG6eIU2qLSauEIODgRS2ODA0r0hrMxB22nTp1sAdJKSUSUDzJuQatF68x5BCo0rxShUgDXfP/99+33YuFe3nXXXfacQD6omK1bt045E9vIkx/SqXiZxiCpgPiE5JUWm++ki2BIJfrBD35gxV7GN6Omqe0UYRwxYoSNzLFTrolYURewPwo4J7ZiM2Af5+f9UtjHdq5Nuh/SiSSDxBkQIPyRSOvrr7+24kQDTb1GoDmnCBbvsCK6oi7QoFNniM5ErLlH5MuNvsJSsGBRiHITwkCm6TLB9OnTC8qstJKoOhVZxpO4GSxEc4TfpQA7eWeYdM8QTsL8kSNH2rywTovCtnzYvHmzPYZzUfDYKHCPiEgpaLGPli7sPc+GdD2lKy3jCjLWSPoTTzyR1m1HoNmHbdLo4MQyRkQry/2QH024Xwj63//+d1uRSCP/ODOVSOA8nI8KjG00DFKWnFcilUJoajsRRgEfoWLTHVqwYIG1z/VhzotwFAqD40Q+XIfzIY74z/Dhw23eSReRdCH6Iw/kjX0QYUQXX2estl+/flZ82Ic6z73aunWrueeee+x1uCdEiNwDAT/mHrKN6yHgfGd//FnGvvPFvsCPi+f7cjBurPya4IcQWAbBUXu6THSfcg2M46xhQmS5NrjiJ8fT3QyK9oJoqhejiQ2MG4TNa77oC/yaD+X2Aj/AZiJwl4IFq7mggpVsVLCaL0GCFdmvhEp+EBXSBSiVWClKc0QFS1GUxKCCpShKYlDBUhQlMahgKYqSGFSwFEVJDCpYiqIkBhUsRVESQ+rBUUVRlLiR8Ul3/4ZyoTnbXg7lWi6+W451NMhm7RIqipIYVLAURUkMKliKoiQGFSxFURKDCpaiKIlBBUtRlMRQMsHi7Z+8InbJkiVeSulpimsqitJ4hBIsJki4+uqrU++p5i2Z7sI2mfqnEHj7Ju+HXrVqlV1HcPzXuP766+11ZL3YazYViCq28tkckTepJrFs8qFc7BSok3EIBHIKFhXrgQcesC+y56X8MHPmTDvDBsszzzxj0zIxa9asNOHhhf9+NmzYYD9lJpyxY8ea5cuXW5Hi3e5c44UXXjCvvfZaZNcsBa7QZipcHoa78MIL095tH+a4uCCNlzQufph0k5lX3EkdINdxccItDxoXxMlPkJ3YJsfRsCehUZJeSbY8Y//27dvNqFGjvJT041gaq1xzChazezBDCDNryGQPriDcdNNNNi0Trrix3Hbbbd6WE6xYscJWYjk/xjOrCSLFjClcI5+KHOaaUUOeKVS5Jt+DCvHTTz9NK/iwx8UB8iWNVya2bNliLrvsMm+tgTDHxQWElQaUBpPywC+DJlrx20kFZkYn5lfkuNtvv93WnTiDED399NPmvvvus3nmk3W/QCPOAwcOTGtksQ0bOQ6bsb0xBDqnYFHZWYhS7rjjDjvNT6YIC8cUIWNqJOYw80c7/sqIkXv27EmrxHDttdea3/zmN/ZafGaikGuWAkT3kksu8daM/U6aC5Xh8OHDaQUf5rg4gBN/8skn1qG7d+/upaZDWTIPHTNhC2GOixPMzu2fgso/+UOQnUA05pYt02PFGYQIxA75lHSBqenPPvtsb62hTCdNmmTnWhQoW/eelYpQY1hUeGllMMYfYZHmTg+PiImgBQmbC10kjPVP/4VDVFdX2++PPPKI/Y5DyDX95HPNqKEAESKcXeA7aW5rtXbtWnPuued6a+GPiwM443XXXZfVKSlLKqm7T5jj4gR+SF6lIQS3YkKQnXKcdH1pdBjaiDPM2di+ffuUHXyyLnM5AuKMP7rizH7Yi49SJxF4BMy9H6Uip2BRAISKzCv42GOPpQkCYfOYMWPsWFMh3S4MJpR0IwyBab+Z1JFCJ8oSJLpjPMs/ThJnsBXRbYoZqxsLf3c3ySBS+Bn4hyOy2YlP4pv4dGONnZYSxBlbgsSINIaKmM2doCIWXUIiJwkRyZREViyMMy1dutSONbmFSgTk7scSFBVx3oMHDwb+Fzrn5fwcS0SXi7DXLAVBLZO/9WJcpF27dmkFH+a4pBDU3W0O0B1kXFEIa2dcI2UXfx75ZF0iftaJFHO9JQJf7dChQ5ofl4pQY1gS4YwfP96GhhLluBEWkZC0SkELx3Cs2/2hi1RRURFY+JxXBj7dCEug9WLJ95qlwj/25B+b+uc//2mGDh3qrZ0g13FJwd/dTSo0vG5kxGSe7lhUJjvpQrq/KCah4fGPWcmnm44N/vpJJMV4NuIN2Hzo0KFGqWehxrAElJa59ufNm5fKrAuFRv+dXw0QMaIKChEHIISmWzl//nxrIMcvWrQosBJD2Agrn2uWEoQTx5boju8y9oGte/fuTTmCS7bj4ob83E9ETfQqFRQH/sc//pGxJc50XByRcScpD6IrSctmJ2XGL4riswx1UFfiDGJ68803219wyTOfrIvI0rsKEmcEjHErfiXkOMavpkyZ0jjRNS/w27JlCx8ZqaqqqqsXg7r6VsMufH/ppZfqKisr60aOHGm31/d17frjjz9eV1NTUzdjxgz7/aOPPrL78Ml+8j0bbOd4zgMcx8L5OF6W+hta9DVz2Z5kmrNtQjnYCOVip0uQzS34w8Barn5qc6U5214O5VouvluOdTTI5ry6hIqiKE2JCpaiKIlBBUtRlMSggqUoSmJQwVIUJTGoYCmKkhhUsBRFSQwqWIqiJIbUg6OKoihxw//gaEqw/C8pKxf459bmantztk0oBxuhXOx0wWZ90l1RlMSigqUoSmJQwVIUJTGoYCmKkhhUsBRFSQwqWIqiJAYVLEVREkPJn8Ni5mZgynmBd0VXVVWZhx9+2L4Hmvd7z5kzJ3CGXeGKK64w06dPj/yl/mGeb3l317vm5S0vm8PHDnsphdG+dXsz4ewJ5ic9f+KllJZstiXVJj+5yq9c7ITmYqvQqM9h8cJ+XsLP5AvnnXeeufjii1PL7Nmzzfr1681VV11lZ+KRaZQmTpxo3nvvPfPUU0+ZHj16mBdffNGuk96UROEEwDk4V7GsXr3a3tti5oGLi03btm2zPoBNgqThK83BThpo8f37778/NQEHNku6NOzFEJcyxT7sFNuw359O+VLO+VLSLiFREVHTXXfdZe6++24rPix8Hzx4sHnjjTfs7CIyjdLChQutMbfccovZvXu3nUiVddKbkiicQCj2XFTeZcuWmR/96EdeSmHEwSYq7EMPPWSGDRvmpTTY9/zzz5vnnnvO+gqROQ1XoTS1nVTKTZs2mbffftvawywzzPBEOuUo6X379k1V7EKJQ5kC9mEndmEf9mMvZTpu3DibznfKOd/GqGSCRVeP6bcQrV/+8pd2fn4mYkWA3AiLFnT//v32mLhGWI0BlVdaHWmJ/K0u6c8++6yprKy0k7LGGSqfREcsfHcrJLZs3rzZTsfWrVs3L7VBsJiUU7r+zKRMlJ6vYzcWueykHtx6661pQxm9e/c269atMwMGDEilDxkyxFZs7kuc8dvo2i8gVviogK+2bNnSlqPM1s59odyDpgvMRskEi4pHhESE9ec//9m8//77toAQIHdhjsPOnTvbY+IaYWXixsE3mnkV88wlvU5MfDr9/OlmwZUL7OLflg26zQg0rc7ll19uWyJ33A9oubiH/fv391Kih/ySb2wTCrEJh2WMctq0aeaGG24wM2bMSHNiKuqECRNOGpPEkZmUUyquOLR/v2KJquxy2Yk95F26f0BZ79ixwwqX4Lc7SoLK9JpzrjF/+e+/pOx1t2WDfFJnAXuwg3XSBYINoMGlDhOYHD9+PK0hAqLKnTt3emvhKJlgUano7tH9I8oiNKSAMNJdiCSATxExf4TFwvaonbYYBp0+yAw7Y5ipras1P+nVMDhJofdq38v87sPfmUn/N8k8uvpRmx4W7KPVobssLZGAw+McbmUoBWLLwK4DrY3F2IQ9lDldPnHiXOD4iDVOjn/QeLEeZdlHXXZh7ESk8GNwI7DGwF+mCFhFnwrz+mevW1tZdh7OTzhEbC+66CL7GYR051955ZW8hSkTJRMsWgpEBqE6ePCg/RWQLoCMXVF4iBmsWbMmTcT8EZYsVNq4MPD0gaZVy1bm028/tY6OI5zT5Rzz8Vcfmw1fb7D78LniixPT0OeCFgkHoMWeO3duKszmXvKrqkSgRGB8p0Unko0KbMCWjd9sNG2/19baWKhN5PnJJ580kydPtgvfw0YPUrlpuBgOYD1Koiy7fO2kotPw+KMLytofgURBUJkOPG2gOfDdAbNo8yJvL2P+uu2v3rfcUA/pMVFGfGarl9hDl5AIyx9B+qPMMJRUsBCqXr16mY4dO9rC+PLLL72t6QwfPtwaj5AhaC4SnbE9ascthh92+aEt9A92f2Cdf1TvUaZdq8LHlSh0nBgbiTKYCvzNN9+02yh0NwLlflCRGbiMsnsoFRmbsO3cM88t2Ca6rxUVFTZ/LNdee63Ne1gQYkSZRitqoiy7XHYSTbljkYgU5ewfs/KPaUWFv0yx/Yy2Z3hb8wdhRaRoLIEoikDEbVzxVREx1qurq02fPn3SxqzY3x3TCkvJBIsM9ezZM/ULIAOPRA8y2E6kwOC7QKGSTvgvXUIqJOC0UUYSxSKtVu8Ovc3NQ282HU/paPp36m++OPyFbakLAaHyj30wxtOY4MzYgk3Y1qNdD1NdW12QTdjiNjBUZiJDFyozfoAwEVXj6Dg4zk6ZI8ru2EgURF12ueyUMpVegnTr2Q+hY183PWr8ZXp257PNkf8cMZ1O6RRqjM4P5YFIucKKn0o5kU5jS33GLuwTQUfk6CmQznci0nzLt+QPjuKUK1eutA99bty40RoiD4zKtq5du5p9+/alHgzFYR988EHzxz/+0RqKWN15551m9OjRJw1EF0uYB/KmvDPF+9YAg7M4/dNrn7ZdBwYwx/QbY5ZuX2ou6H6BdQyoPV5rxwnc0BvmXzbf+1Zastnmt8m1gfxSsXFyKnKXNl1iY5OfXOWX1LLzU4ifZivTr2q+Mj8966fensas37fezFk5x1troKlsFYIeHC25YMWdQhyhWOIoWMWSFMEqliQJVrHEUbBK1iVsTvCvClER5bmKoTnaFES52AnlYKsKVgj4v6ooCpBzcK440BxtCqJc7IRysFW7hCFC7aTSnG0TysFGKBc7XbRLqChKotEIK0vLVbtjmandtNDUfXfISymeFqd0MK0GTDSt+lZ4KaVDI6zmQy47k+6rQWiElSdROwBwPs5bKDzi4X8di6LE0Vd5hEmerXPJlB4GFawsRO0AQqHnRaT8r2NRFIiTr8rT7jzhzn+4CJnS80EFKyYgRtleL0Na0OtYFKUx4T9Ycr1ehgfE+Y8V/k3JJVN6Pqhg5Un7S2eZzuOrUkunsf9rOox+0nSsX4S0ff5nkTl1UO7/h+PfO7K9Xob/AAh6HYuiBNF2xK1pfoofdhg123SqXGBa973M7oNfki774Le54D9Ucr1eBl92/11JyJSeDypYeXJ4+Uxz+N17zfGafea7bW+aA0uuM3VHvva2nuD4gc/N/sXjzP5XrzFHNoR7YyZilOn1MoqSDzWrnrT+hx/W7l1j/bD2q3Xe1hPU1Vab6pVz7b74dljCvF6mFKhgxQi6gEGvl1GUOMHwRdjXy0SNClaJaNmpjw2z3a5iNij0TK+XUZRS0aJVO9Pu/Kl2aEO6itmgEc32eplSo4JVIqRLePCtW72U7CBU7utFEC3/62UyvY5FUQpFuoQMbRzb8Y6Xmhn8MtvrZUAG5nlFEG8dZkyWBjlTej7og6NZHsireT34/6lanTnMtK1vlWr3rLJjBQxWtuo23G6rq60xx6u/Mt+rj7Asx2vN0U8WnTSO1bay+Om+cqEPjjYfctmZyVeJ8I8f+dqOTzHI3ua/rqkPU1rZbf/5dmu9n/ZNrTPWFTSO1Ri+GkTQg6MqWAUIVhSoYEWDClYDSffVIIIES7uEWeBfE0pBqc6rlC/l4qsqWFng/6iiLjDOx3kVJUrKxVe1S9iMuxTaJWw+lIudLtolVBQl0ahgKYqSGFSwFEVJDFawWrZU3VIUJf6kBIuppBVFUeIAetSqVcMDrS72V8IDBw7Yx+Zra2u9ZEVRlKYDseLffTp16uSlNGAFiy9Hjx41x44dM96qoihKk9CiRQvTunVr06ZNGy/lBCnBUhRFiTfG/D/7jbesy/MiRQAAAABJRU5ErkJggg==)
解説の理解
今回の解説については、1つ目が分かっていれば(自力で思いつくかはともかく)理解は容易でしょう。
実装について、行列の演算となるとnumpy
を使いたくなります。特に累乗となるとnumpy.linalg.matrix_powerが使えそう。
ですが、実際に使ってみると計算途中で数字がオーバーフローしてしまいます。
オーバーフロー例①
import numpy as np
mod = 1_000_000_007
def kaisetsu2_1(N, B, K, c):
A = np.zeros((B, B), dtype=np.int64)
for i in range(B):
for j in c:
nex = (i*10 + j) % B
A[i][nex] += 1
return (np.linalg.matrix_power(A, N)[0][0]) % mod
# 5は終わらない
test_all(kaisetsu2_1, 4)
オーバーフロー例②
import numpy as np
mod = 1_000_000_007
def mat_pow(a, n):
ret = np.eye(*a.shape, dtype=a.dtype)
while n:
if n & 1:
ret = ret @ a % mod
a = np.linalg.matrix_power(a, 2)
n >>= 1
return ret
def kaisetsu2_2(N, B, K, c):
A = np.zeros((B, B), dtype=np.uint64)
for i in range(B):
for j in c:
nex = (i*10 + j) % B
A[i][nex] += 1
return mat_pow(A, N)[0][0]
# 5は終わらない
test_all(kaisetsu2_2, 4)
結局、以下のように行列の乗算の過程で余りを取る必要があり、もはやnumpy
を使う必然性がありません。
import numpy as np
mod = 1_000_000_007
def mat_mul(a, b):
ret = np.zeros((a.shape[0], b.shape[1]), dtype=a.dtype)
for i in range(a.shape[0]):
for j in range(b.shape[1]):
ret[i][j] = sum(a[i] * b[:, j] % mod)
return ret % mod
def mat_pow(a, n):
ret = np.eye(*a.shape, dtype=a.dtype)
while n:
if n & 1:
ret = mat_mul(ret, a)
a = mat_mul(a, a)
n >>= 1
return ret
def kaisetsu2_3(N, B, K, c):
A = np.zeros((B, B), dtype=np.uint64)
for i in range(B):
for j in c:
nex = (i*10 + j) % B
A[i][nex] += 1
return mat_pow(A, N)[0][0]
# 5は終わらない
test_all(kaisetsu2_3, 4)
提出 #32513582 - 競プロ典型 90 問
解説③
最後に追加の制約なし(小課題3)でACとなるための解説です。
kyopro_educational_90/005-03.jpg at main · E869120/kyopro_educational_90
想定コード
kyopro_educational_90/005-03.cpp at main · E869120/kyopro_educational_90
Pythonで書き直したのが以下です。
というか けんちょんさんの記事も参考に大分変更を加えました。
from itertools import accumulate
def kaisetsu3(N, B, K, c):
MOD = 1000000007
# python3.8以降
# *ten, = accumulate(range(62), lambda acc, _: (acc ** 2) % B , initial=10)
# python3.7以前
*ten, = accumulate(range(10, 72), lambda acc, _: (acc ** 2) % B)
def mul(x, exp, y):
res = [0] * B
for p in range(B):
for q in range(B):
nex = (ten[exp] * p + q) % B
res[nex] += x[p] * y[q]
res[nex] %= MOD
return res
# 初期化
## doubled:1桁目(2^0)を求める
doubled = [0] * B
for k in c:
doubled[k%B] += 1
## ans:Nの1ビット目を見る
if N & 1:
ans = doubled
else:
ans = [0] * B
ans[0] = 1
N >>= 1
# Nの2ビット目以降見ながらダブリング実施
exp = 0
while N:
# 2^epx桁目から2^(exp+1)桁目を計算
doubled = mul(doubled, exp, doubled)
exp += 1
if N & 1:
ans = mul(ans, exp, doubled)
N >>= 1
return ans[0]
# 5つ目のケース(N = 10^18)は、この環境ではめっちゃ時間掛かる
# test_all(kaisetsu3, 5)
test_all(kaisetsu3, 4)
結果
AC!
提出 #32588657 - 競プロ典型 90 問
長かった…
解説の理解
ダブリングの考え方についても、けんちょんさんの記事(同上)が詳しいです。(丸投げ)
競プロ典型 90 問 005 - Restricted Digits(★7) - けんちょんの競プロ精進記録
まとめ
理解はできた(と思う…)が、自力で解ける気がしない😇
自由欄