PROBLEM LINK:
Author: Sunita Sen
Tester: Soham Chakrabarti
Editorialist: Sunita Sen
DIFFICULTY:
MEDIUM-HARD
PREREQUISITES:
Dynamic Programming - Digit DP
PROBLEM:
Given a string S ,count the number of strings which come before string S( including S) in the dictionary and are of the same length as S such that total sum of character values at prime position is a prime number.
EXPLANATION:
This problem can be solved using Digit DP.
However, instead of digits here we are using characters.
This is a really cool blog explaining Digit DP.
Detailed editorial will be updated soon.
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define dfor(i,a,b) for(ll i=(a);i>=(b);i--)
#define mem(u, vis) memset(u, vis, sizeof(u))
#define ll long long
#define ull unsigned long long
#define MOD 1000000007
#define MAX 1e9
#define pb push_back
#define F first
#define S second
ll dp[2000][10000][2];
// smaller ? 0 - no 1: yes
vector<bool> isprime(100000, true);
void prime(int n){
isprime[0] = isprime[1] = false;
for (int i = 2; i <= n; i++) {
if (isprime[i] && (long long)i * i <= n) {
for (int j = i * i; j <= n; j += i)
isprime[j] = false;
}
}
}
ll calc_dp(string s, ll pos, ll sum, ll smaller){
if(pos == s.length()){
if(isprime[sum]){
return 1;
}
return 0;
}
if(dp[pos][sum][smaller] != -1){
return dp[pos][sum][smaller];
}
ll limit = 'z' - 'a';
ll res = 0;
bool primepos = isprime[pos];
if(!smaller){
limit = s[pos] - 'a';
}
for(ll i = 0; i <= limit ; ++i){
ll ns;
if(i < limit){
ns = 1;
}
else
ns = smaller;
if(primepos){
res = (res + calc_dp(s, pos + 1, sum + i, ns)%MOD)%MOD;
}
else{
res = (res + calc_dp(s, pos + 1, sum, ns)%MOD)%MOD;
}
}
dp[pos][sum][smaller] = res;
return res;
}
signed main() {
ll t=1;
cin>>t;
prime(100000);
while(t--){
string s;
cin>>s;
mem(dp,-1);
cout<<(calc_dp(s,0,0,0))%MOD<<endl;
}
}
Tester's Solution
/* nuttela - Soham Chakrabarti */
#include <bits/stdc++.h>
using namespace std;
#define io ios_base::sync_with_stdio(false);cin.tie(NULL)
#define all(v) v.begin(),v.en()
#define pb push_back
#define ins insert
#define rep(i,j,k) for(ll i=j;i<k;i++)
#define per(i,j,k) for(ll i=j;i>=k;--i)
#define scan(a,n) rep(i,0,n)cin>>a[i]
#define input freopen("input.txt","r",stdin)
#define output freopen("output.txt","w",stdout)
#define error freopen("error.txt","w",stderr)
#define ff first
#define ss second
typedef long long int ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair <ll,ll> pll;
const int N = 1e6+6;
const int M = 5000;
const int LIM = 1e3;
const int SUM = 5000;
const int ALPHA = 26;
const int EDGE = 2;
const int inf = INT_MAX;
const int mod = 1e9+7;
vector<int> primes;
ll nI[N],fI[N],fact[N],dp[LIM][EDGE][SUM];
string s;
int len;
ll max(ll a,ll b){return a>b?a:b;}
ll min(ll a,ll b){return a<b?a:b;}
ll gcd(ll a,ll b){while(b){ll t=a;a=b;b=t%b;}return a;}
ll lcm(ll a,ll b){return (max(a,b)/gcd(a,b))*min(a,b);}
ll power(ll a,ll b){ll r=1;while(b){if(b&1)r*=a;a=a*a;b>>=1;}return r;}
bool isPrime(ll n){if(n<=1)return 0;if(n<=3)return 1;if(n%2==0||n%3==0)return 0;for(ll i=5;i*i<=n;i+=6)if(n%i==0||n%(i+2)==0)return 0;return 1;}
void find_primes(ll n=M){ll limit=floor(sqrt(n))+1;vector<int> test;test.pb(2),primes.pb(2);for(ll i=3;i<limit;i+=2)if(isPrime(i))test.pb(i),primes.pb(i);ll lo=limit,hi=2*limit;bool p[limit];while(lo<n){if(hi>n)hi=n;memset(p,true,sizeof(p));for(int i=0;i<test.size();++i){ll mn=(lo/test[i])*test[i];if(mn<lo)mn+=test[i];for(ll j=mn;j<hi;j+=test[i])p[j-lo]=0;}rep(i,0,limit)if(p[i] && i+lo<hi)primes.pb(i+lo);lo+=limit,hi+=limit;}}
ll modmult(ll a,ll b){ll r=0;a%=mod;while(b){if(b&1)r=(r+a)%mod;a=(a<<1)%mod;b>>=1;}return r;}
ll modexpo(ll a,ll b){ll r=1;a%=mod;while(b){if(b&1)r=(r*a)%mod;a=(a*a)%mod;b>>=1;}return r;}
ll nCr(ll n,ll r){ll res=1;if(r>n>>1)r=n-r;rep(i,0,r){res=(res*(n-i))%mod;res=(res*modexpo(i+1,mod-2))%mod;}return res;}
void binomial_pre(){nI[0]=nI[1]=fI[0]=fI[1]=fact[0]=1;rep(i,2,N)nI[i]=nI[mod%i]*(mod-mod/i)%mod;rep(i,2,N)fI[i]=(nI[i]*fI[i-1])%mod;rep(i,1,N)fact[i]=(fact[i-1]*i)%mod;}
ll binomial(ll n,ll r){if(n<r)return 0;return ((fact[n]*fI[r])%mod*fI[n-r])%mod;}
ll work(ll idx,ll edge,ll sum) { //edge - {1,0}
//cout<<idx<<' '<<edge<<' '<<sum<<endl;
if(idx==len) {
if(isPrime(sum))
return 1;
return 0;
}
ll ans=dp[idx][edge][sum],tot=0,hi,e;
if(ans!=-1)return ans;
bool isp=isPrime(idx);
if(edge)
hi=s[idx]-'a'+1;
else
hi=ALPHA;
rep(i,0,hi) {
if(isp) {
tot=(tot+work(idx+1,(i<hi-1?0:edge),sum+i)%mod)%mod;
}
else {
tot=(tot+work(idx+1,(i<hi-1?0:edge),sum)%mod)%mod;
}
}
dp[idx][edge][sum]=tot;
return tot;
}
int32_t main() {
io;
// input; output;
find_primes();
int t;
cin>>t;
while(t--) {
cin>>s;
len=s.size();
memset(dp,-1,sizeof(dp));
cout<<work(0,1,0)%mod<<endl;
}
return 0;
}