Prime Digit Sums
Problem Statement :
Chloe is fascinated by prime numbers. She came across the number 283002 on a sign and, though the number is not prime, found some primes hiding in it by using the following rules: Every three consecutive digits sum to a prime: 283002 283002 283002 283002 Every four consecutive digits sum to a prime: 283002 283002 283002 Every five consecutive digits sum to a prime: 283002 283002 You must answer q queries, where each query consists of an integer, n. For each n, find and print the number of positive n-digit numbers, modulo 10^9 + 7, that satisfy all three of Chloe's rules (i.e., every three, four, and five consecutive digits sum to a prime). Input Format The first line contains an integer, q, denoting the number of queries. Each of the q subsequent lines contains an integer denoting the value of n for a query. Constraints 1 <= q <= 2 * 10^4 1 <= n <= 4 * 10^5 Output Format For each query, print the number of n-digit numbers satisfying Chloe's rules, modulo 10^9 +7, on a new line.
Solution :
Solution in C :
In C++ :
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define mod 1000000007;
typedef long long ll;
int func(int n){
int sum=0;
while(n){
sum+=n%10;
n/=10;
}
return sum;
}
int p[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43};
int main(){
bool num3[1000],num4[10000];
int num5[100000];
for(int i=0;i<1000;i++){
num3[i]=false;
}
for(int i=0;i<10000;i++){
num4[i]=false;
}
for(int i=0;i<100000;i++){
num5[i]=-1;
}
int a=0,b=0,d=0;
int count1=0;
for(int i=0;i<1000;i++){
for(int j=0;j<14;j++){
if(func(i)==p[j]){
num3[i]=true;
//cout<<i<<endl;
count1++;
if(i>=100)
a++;
}
}
}
////cout<<" count of 3 "<<count1<<endl;
int count2=0;
for(int i=0;i<10000;i++){
if(num3[i%1000]&&num3[i/10]){
for(int j=0;j<14;j++){
if(func(i)==p[j]){
num4[i]=true;
//cout<<i<<endl;
count2++;
if(i>=1000)
b++;
}
}
}
}
//cout<<"Count of 4 "<<count2<<endl;
int count=0;
vector<int> num;
for(int i=0;i<100000;i++){
if(num4[i%10000]&&num4[i/10]){
for(int j=0;j<14;j++){
if(func(i)==p[j]){
num5[i]=count;
//cout<<i<<endl;
count++;
num.push_back(i);
if(i>=10000)
d++;
}
}
}
}
//cout<<"count of 5 "<<count<<endl;
// cout<<count<<endl;
vector<int> gr[count];
int count3=0;
for(int i=0;i<count;i++){
int temp=num[i];
temp/=10;
for(int j=0;j<count;j++){
if(temp==num[j]%10000){
gr[i].push_back(j);
//cout<<i<<" "<<j<<" "<<num[i]<< " "<<num[j]<<endl;
count3++;
}
}
}
//cout<<count3<<endl;
ll dp[2][count];
for(int i=0;i<count;i++){
dp[0][i]=1;
if(num[i]<10000){
dp[0][i]=0;
}
}
ll res[400007];
res[1]=9;
res[2]=90;
res[3]=a;
res[4]=b;
res[5]=d;
int r=1,c=0;
for(int i=6;i<400001;i++){
res[i]=0;
for(int j=0;j<count;j++){
dp[r][j]=0;
for(int k=0;k<gr[j].size();k++){
dp[r][j]+=dp[c][gr[j][k]];
}
dp[r][j]%=mod;
res[i]+=dp[r][j];
}
res[i]%=mod;
r=1-r;
c=1-c;
}
int q;
scanf("%d",&q);
for(int a0 = 0; a0 < q; a0++){
int n;
scanf("%d",&n);
cout<<res[n]<<endl;
//cout<<count<<endl;
}
return 0;
}
In Java :
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
public static boolean isPrime[] = new boolean[46];
public static int results[] = new int[400001];
public static boolean isGood(int n, int val) {
int max = Math.min(n, 5);
int mod = 100;
for (int i = 3; i <= max; i++) {
mod *= 10;
int d = val;
for (int j = 0; j < (max - i + 1); j++) {
int d2 = d % mod;
int sum = 0;
while (d2 > 0) {
sum += d2 % 10;
d2 /= 10;
}
if (!isPrime[sum]) {
return false;
}
d = d / 10;
}
}
return true;
}
public static void initSimple() {
for(int i=100; i<1000; i++) {
if(isGood(3,i)) {
results[3]++;
}
}
for(int i=1000; i<10000; i++) {
if(isGood(4,i)) {
results[4]++;
}
}
results[1]=9;
results[2]=90;
}
public static void init() {
Arrays.fill(isPrime, 0, isPrime.length, true);
isPrime[0] = false;
isPrime[1] = false;
for (int i = 2; i < 45; i++) {
if (isPrime[i]) {
for (int j = 2; j < i; j++) {
if (i % j == 0) {
isPrime[i] = false;
}
}
}
}
ArrayList<Integer> good = new ArrayList<Integer>();
for (int i = 0; i < 100000; i++) {
if (isGood(5, i)) {
good.add(i);
}
}
List<Integer> childs[] = new List[good.size()];
for (int i = 0; i < good.size(); i++) {
int val = (good.get(i) % 10000) * 10;
childs[i] = new ArrayList<Integer>();
for (int j = 0; j < 10; j++) {
if (good.contains(val + j)) {
childs[i].add(good.indexOf(val + j));
}
}
}
int buf1[] = new int[good.size()];
int buf2[] = new int[good.size()];
int temp[];
int count = 0;
for (int i = 0; i < buf1.length; i++) {
if (good.get(i) >= 10000) {
buf1[i] = 1;
count++;
}
}
results[5] = count;
int idx = 0;
for (int i = 6; i < results.length; i++) {
Arrays.fill(buf2, 0, buf2.length, 0);
count = 0;
for (int j = 0; j < buf1.length; j++) {
if (buf1[j] > 0) {
List<Integer> next = childs[j];
for (int k = 0; k < next.size(); k++) {
idx = next.get(k);
buf2[idx] += buf1[j];
buf2[idx] %= 1000000007;
count += buf1[j];
count %= 1000000007;
}
}
}
results[i]=count;
temp=buf1;
buf1=buf2;
buf2=temp;
}
}
public static void main(String[] args) {
init();
initSimple();
Scanner in = new Scanner(System.in);
int q = in.nextInt();
for(int a0 = 0; a0 < q; a0++){
int n = in.nextInt();
System.out.println(results[n]);
}
}
}
In C :
#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef unsigned long long ull;
typedef unsigned int ui;
#define swap_(x, y)
{
ui *z = x;
x = y;
y = z;
}
#define ac 20
#define ec (18 * 18)
#define mod 1000000007
#define brutec 13
ui brutes[] = {0, 9, 90, 303, 280, 218, 95,
101, 295, 513, 737, 668, 578}; // see haskell file
ui as[ec * ac];
ui startv[] = {17, 6, 6, 2, 0, 0, 9, 3, 9, 3, 0, 0, 6, 4, 13, 15, 13, 15};
ui endv[] = {5, 11, 11, 26, 20, 20, 7, 7, 7, 5, 24, 24, 5, 5, 2, 2, 2, 1};
// 18x18 times 18x18
void multmm(ui *a, ui *b, ui *c) {
for (int i = 0; i < 18; ++i) {
for (int j = 0; j < 18; ++j) {
ull x = 0;
for (int k = 0; k < 18; ++k) {
x += (ull)a[i * 18 + k] * (ull)b[k * 18 + j];
}
c[i * 18 + j] = (ui)(x % mod);
}
}
}
// 18x18 times 18x1
void multmv(ui *a, ui *b, ui *c) {
for (int i = 0; i < 18; ++i) {
ull x = 0;
for (int k = 0; k < 18; ++k) {
x += (ull)a[i * 18 + k] * (ull)b[k];
}
c[i] = (ui)(x % mod);
}
}
// 1x18 times 18x1
ui inprod(ui *a, ui *b) {
ull x = 0;
for (int k = 0; k < 18; ++k) {
x += (ull)a[k] * (ull)b[k];
}
return (ui)(x % mod);
}
void copy(ui *a, ui *b, int n) {
for (int i = 0; i < n; ++i) {
a[i] = b[i];
}
}
void ini() {
ui _a[] = {
0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0,
0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
ui _b[ec];
ui *a = _a, *b = _b;
for (int i = 0; i < ac; ++i) {
copy(&as[i * ec], a, ec);
multmm(a, a, b);
swap_(a, b);
}
}
ui solve(int n) {
if (n < brutec) {
return brutes[n];
}
n -= 12;
ui _v[18], _u[18];
ui *v = _v, *u = _u;
copy(v, startv, 18);
ui *a = as;
while (n) {
if (n % 2) {
multmv(a, v, u);
swap_(v, u);
}
n /= 2;
a += ec;
}
return inprod(v, endv);
}
int main() {
ini();
int q;
scanf("%d", &q);
for (int i = 0; i < q; ++i) {
int n;
scanf("%d", &n);
ui x = solve(n);
printf("%u\n", x);
}
return 0;
}
In Python3 :
mod = 10**9 + 7
A = [0,0,0,0,0,2,3,15,2,0]
B = [0,0,0,0,0,4,9,13,17,2]
results = [1,9,90,303,280,218,95,101,295]
for _ in range(int(input())):
n = int(input())
for i in range(len(A),n):
A.append((2*(A[i-5] + B[i-5])) % mod)
B.append((A[i-1] + A[i-5] + 2*B[i-5]) % mod)
print(results[n] if n < 9 else
(5*A[n-1] + 9*A[n-2] + 19*A[n-3] + 6*A[n-4] + 3*A[n-5]
+ 2*B[n-1] + 5*B[n-2] + 20*B[n-3] + 5*B[n-4] + 4*B[n-5]) % mod)
View More Similar Problems
Pair Sums
Given an array, we define its value to be the value obtained by following these instructions: Write down all pairs of numbers from this array. Compute the product of each pair. Find the sum of all the products. For example, for a given array, for a given array [7,2 ,-1 ,2 ] Note that ( 7 , 2 ) is listed twice, one for each occurrence of 2. Given an array of integers, find the largest v
View Solution →Lazy White Falcon
White Falcon just solved the data structure problem below using heavy-light decomposition. Can you help her find a new solution that doesn't require implementing any fancy techniques? There are 2 types of query operations that can be performed on a tree: 1 u x: Assign x as the value of node u. 2 u v: Print the sum of the node values in the unique path from node u to node v. Given a tree wi
View Solution →Ticket to Ride
Simon received the board game Ticket to Ride as a birthday present. After playing it with his friends, he decides to come up with a strategy for the game. There are n cities on the map and n - 1 road plans. Each road plan consists of the following: Two cities which can be directly connected by a road. The length of the proposed road. The entire road plan is designed in such a way that if o
View Solution →Heavy Light White Falcon
Our lazy white falcon finally decided to learn heavy-light decomposition. Her teacher gave an assignment for her to practice this new technique. Please help her by solving this problem. You are given a tree with N nodes and each node's value is initially 0. The problem asks you to operate the following two types of queries: "1 u x" assign x to the value of the node . "2 u v" print the maxim
View Solution →Number Game on a Tree
Andy and Lily love playing games with numbers and trees. Today they have a tree consisting of n nodes and n -1 edges. Each edge i has an integer weight, wi. Before the game starts, Andy chooses an unordered pair of distinct nodes, ( u , v ), and uses all the edge weights present on the unique path from node u to node v to construct a list of numbers. For example, in the diagram below, Andy
View Solution →Heavy Light 2 White Falcon
White Falcon was amazed by what she can do with heavy-light decomposition on trees. As a resut, she wants to improve her expertise on heavy-light decomposition. Her teacher gave her an another assignment which requires path updates. As always, White Falcon needs your help with the assignment. You are given a tree with N nodes and each node's value Vi is initially 0. Let's denote the path fr
View Solution →