Submission #6361394
Source Code Expand
package main import ( "bufio" "fmt" "os" "strconv" ) func getScanner(fp *os.File) *bufio.Scanner { scanner := bufio.NewScanner(fp) scanner.Split(bufio.ScanWords) scanner.Buffer(make([]byte, 500001), 500000) return scanner } func getNextString(scanner *bufio.Scanner) string { scanner.Scan() return scanner.Text() } func getNextInt(scanner *bufio.Scanner) int { i, _ := strconv.Atoi(getNextString(scanner)) return i } func getNextInt64(scanner *bufio.Scanner) int64 { i, _ := strconv.ParseInt(getNextString(scanner), 10, 64) return i } func main() { fp := os.Stdin if len(os.Args) > 1 { fp, _ = os.Open(os.Args[1]) } scanner := getScanner(fp) writer := bufio.NewWriter(os.Stdout) d := getNextInt(scanner) n := getNextString(scanner) l := len(n) var dp [10001][2][100]int dp[0][0][0] = 1 mod := 1000000007 for i := 0; i < l; i++ { num := int(n[i] - '0') for ii := 0; ii < 2; ii++ { for iii := 0; iii < d; iii++ { if ii == 0 { dp[i+1][0][(iii+num)%d] = (dp[i+1][0][(iii+num)%d] + dp[i][ii][iii]) % mod for iiii := 0; iiii < num; iiii++ { dp[i+1][1][(iii+iiii)%d] = (dp[i+1][1][(iii+iiii)%d] + dp[i][ii][iii]) % mod } continue } for iiii := 0; iiii < 10; iiii++ { dp[i+1][1][(iii+iiii)%d] = (dp[i+1][1][(iii+iiii)%d] + dp[i][ii][iii]) % mod } } } } ans := (dp[l][0][0] + dp[l][1][0] - 1) % mod if ans < 0 { ans += mod } fmt.Fprintln(writer, ans) writer.Flush() }
Submission Info
Submission Time | |
---|---|
Task | E - 数 |
User | ccppjsrb |
Language | Go (1.6) |
Score | 4 |
Code Size | 1542 Byte |
Status | AC |
Exec Time | 831 ms |
Memory | 16768 KB |
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 4 / 4 | ||
Status |
|
Set Name | Test Cases |
---|---|
All | 00, 01, 02, 90, 91 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00 | AC | 10 ms | 1280 KB |
01 | AC | 499 ms | 16768 KB |
02 | AC | 831 ms | 16640 KB |
90 | AC | 2 ms | 1152 KB |
91 | AC | 2 ms | 1280 KB |