Typical DP Contest

Submission #1613598

Source codeソースコード

#include <bits/stdc++.h>
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define RREP(i,a,b) for(int i=(a);i>=(b);i--)
typedef long long ll; typedef long double ld;
using namespace std;
const int INF=1e9, MOD=1e9+7;
const int MAX_N=10000;
int d;
string s;
ll dp[100010][2][100];
int tmp[10010][110];

int main(){
	cin >> d >> s;
	
	dp[0][0][0]=1;
	REP(i,0,s.size()) REP(j,0,2) REP(k,0,d){
		int n=(j?10:s[i]-'0'+1);
		
		REP(l,0,n){
			dp[i+1][j|(l+1)<n][(k+l)%d] += dp[i][j][k];
			dp[i+1][j|(l+1)<n][(k+l)%d] %= MOD;
		}
	}

	cout << (dp[s.size()][0][0]+dp[s.size()][1][0]-1+MOD)%MOD << endl;
	return 0;
}
	

Submission

Task問題 E - 数
User nameユーザ名 ecasdqina
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 4
Source lengthソースコード長 635 Byte
File nameファイル名
Exec time実行時間 83 ms
Memory usageメモリ使用量 16640 KB

Test case

Set

Set name Score得点 / Max score Cases
All 4 / 4 00,01,02,90,91

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
00 AC 2 ms 2304 KB
01 AC 52 ms 16640 KB
02 AC 83 ms 16640 KB
90 AC 2 ms 2304 KB
91 AC 2 ms 2304 KB