Counting the Ways
Problem Statement :
Little Walter likes playing with his toy scales. He has N types of weights. The ith weight type has weight ai. There are infinitely many weights of each type. Recently, Walter defined a function, F(X), denoting the number of different ways to combine several weights so their total weight is equal to X. Ways are considered to be different if there is a type which has a different number of weights used in these two ways. For example, if there are types of weights with corresonding weights 1, 1, and 2, then there are 4 ways to get a total weight of 2: 1.Use 2 weights of type 1. 2.Use 2 weights of type 2. 3.Use 1 weight of type 1 and 1 weight of type 2. 4.Use 1 weight of type 3. Given N, L, R, and a1,a2,...,aN, can you find the value of F(L)+F(L+1)+...+F(R)? Input Format The first line contains a single integer, N, denoting the number of types of weights. The second line contains N space-separated integers describing the values of a1,a2,...,aN, respectively The third line contains two space-separated integers denoting the respective values of L and R. Constraints 1 <= N <= 10 0 < ai <= 10^5 a1*a2*...*aN <= 10^5 1 <= L <= R <=10^17
Solution :
Solution in C :
In C++ :
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;
int n;
int a[10];
long long L, R;
const int N = 202000;
int dp0[N];
int dp1[N];
inline void add(int &x, int y) {
x += y;
if (x >= MOD) x -= MOD;
}
long long solve(long long v) {
bitset<62> s(v);
memset(dp0, 0, sizeof(dp0));
dp0[0] = 1;
for (int k = 0; k < 62; k++) {
for (int i = 0; i < n; i++) {
for (int j = N - a[i] - 1; j >= 0; j--) {
add(dp0[j + a[i]], dp0[j]);
}
}
if (s[k]) {
add(dp0[0], dp0[1]);
for (int i = 1; i < N - 1; i++) {
dp0[i] = dp0[i + 1];
}
}
memset(dp1, 0, sizeof(dp1));
for (int i = 0; i < N; i++) {
add(dp1[(i + 1) / 2], dp0[i]);
}
swap(dp0, dp1);
}
return dp0[0];
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
cin >> L >> R;
int ans = solve(R) - solve(L - 1);
if (ans < 0) ans += MOD;
cout << ans << endl;
}
In Java :
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
public class F {
InputStream is;
PrintWriter out;
String INPUT = "";
int mod = 1000000007;
void solve()
{
int n = ni();
int[] a = na(n);
long L = nl(), R = nl();
int Z = 1200000;
long[] dp = new long[Z+1];
Arrays.fill(dp, 1);
long pe = 1;
for(int v : a){
pe *= v;
for(int i = 0;i+v <= Z;i++){
dp[i+v] += dp[i];
if(dp[i+v] >= mod)dp[i+v] -= mod;
}
}
int[][] fif = enumFIF(30, mod);
long ret = 0;
{
long[] y = new long[12];
for(int i = 0;i < 12;i++){
y[i] = dp[(int)(R%pe+i*pe)];
}
ret += guessDirectly(mod, R/pe, fif, y);
}
{
long[] y = new long[12];
for(int i = 0;i < 12;i++){
y[i] = dp[(int)((L-1)%pe+i*pe)];
}
ret -= guessDirectly(mod, (L-1)/pe, fif, y);
}
if(ret < 0)ret += mod;
out.println(ret);
}
public static int[][] enumFIF(int n, int mod) {
int[] f = new int[n + 1];
int[] invf = new int[n + 1];
f[0] = 1;
for (int i = 1; i <= n; i++) {
f[i] = (int) ((long) f[i - 1] * i % mod);
}
long a = f[n];
long b = mod;
long p = 1, q = 0;
while (b > 0) {
long c = a / b;
long d;
d = a;
a = b;
b = d % b;
d = p;
p = q;
q = d - c * q;
}
invf[n] = (int) (p < 0 ? p + mod : p);
for (int i = n - 1; i >= 0; i--) {
invf[i] = (int) ((long) invf[i + 1] * (i + 1) % mod);
}
return new int[][] { f, invf };
}
public static long guessDirectly(long mod, long x, int[][] fif, long... y)
{
int n = y.length;
if(0 <= x && x < n){
return y[(int)x];
}else if(x % mod - (n-1) <= 0){
long mul = 1;
for(int i = 0;i < n;i++){
if((x-i)%mod == 0)continue;
mul = mul * ((x-i)%mod) % mod;
}
long s = 0;
long sig = 1;
long big = 8L*mod*mod;
for(int i = n-1;i >= 0;i--){
if((x-i)%mod == 0){
s += fif[1][i] % mod * fif[1][n-1-i] % mod * y[i] * sig;
if(s >= big)s -= big;
if(s <= -big)s += big;
}
sig = -sig;
}
s %= mod;
if(s < 0)s += mod;
s = s * mul % mod;
return s;
}else{
long mul = 1;
for(int i = 0;i < n;i++){
mul = mul * ((x-i)%mod)%mod;
}
long s = 0;
long sig = 1;
long big = 8L*mod*mod;
for(int i = n-1;i >= 0;i--){
s += invl(x-i, mod) * fif[1][i] % mod * fif[1][n-1-i] % mod * y[i] * sig;
if(s >= big)s -= big;
if(s <= -big)s += big;
sig = -sig;
}
s %= mod;
if(s < 0)s += mod;
s = s * mul % mod;
return s;
}
}
public static long invl(long a, long mod) {
long b = mod;
long p = 1, q = 0;
while (b > 0) {
long c = a / b;
long d;
d = a;
a = b;
b = d % b;
d = p;
p = q;
q = d - c * q;
}
return p < 0 ? p + mod : p;
}
void run() throws Exception
{
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
}
public static void main(String[] args) throws Exception {
new F().run(); }
private byte[] inbuf = new byte[1024];
private int lenbuf = 0, ptrbuf = 0;
private int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) {
throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private boolean isSpaceChar(int c) {
return !(c >= 33 && c <= 126); }
private int skip()
{ int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private double nd() {
return Double.parseDouble(ns()); }
private char nc() { return (char)skip(); }
private String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b)))
{ // when nextLine, (isSpaceChar(b) && b != ' ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}
private int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static void tr(Object... o) {
System.out.println(Arrays.deepToString(o)); }
}
In Python3 :
MOD = 10**9 + 7
def lcm(lst):
ans = 1
for x in lst:
ans = ans*x//gcd(ans, x)
return ans
def gcd(a,b):
if a<b:
a, b = b, a
while b > 0:
a, b = b, a%b
return a
def getsoltable(a, m, MOD=MOD):
soltable = [1] + [0] * (len(a)*m-1)
for x in a:
oldsoltable = soltable
soltable = list(soltable)
for i in range(x, len(soltable)):
soltable[i] = (oldsoltable[i] + soltable[i - x]) % MOD
return soltable
def countsols(const, soltable, lcm):
offset = const % lcm
pts = soltable[offset::lcm]
assert len(pts) == len(a)
coef = polycoef(pts)
return polyval(coef, const//lcm)
def polycoef(pts):
coef = []
for x, y in enumerate(pts):
fact = descpower = 1
for i, c in enumerate(coef):
y -= descpower*c//fact
descpower *= x - i
fact *= i + 1
coef.append(y)
return coef
def polyval(coef, x):
ans = 0
fact = descpower = 1
for i, c in enumerate(coef):
ans += c * descpower * pow(fact, MOD-2, MOD)
descpower = descpower * (x - i) % MOD
fact *= i + 1
return ans % MOD
n = int(input())
a = [1] + [int(fld) for fld in input().strip().split()]
L, R = [int(fld ) for fld in input().strip().split()]
m = lcm(a)
soltable = getsoltable(a, m)
print((countsols(R, soltable, m) - countsols(L-1, soltable, m)) % MOD)
View More Similar Problems
Palindromic Subsets
Consider a lowercase English alphabetic letter character denoted by c. A shift operation on some c turns it into the next letter in the alphabet. For example, and ,shift(a) = b , shift(e) = f, shift(z) = a . Given a zero-indexed string, s, of n lowercase letters, perform q queries on s where each query takes one of the following two forms: 1 i j t: All letters in the inclusive range from i t
View Solution →Counting On a Tree
Taylor loves trees, and this new challenge has him stumped! Consider a tree, t, consisting of n nodes. Each node is numbered from 1 to n, and each node i has an integer, ci, attached to it. A query on tree t takes the form w x y z. To process a query, you must print the count of ordered pairs of integers ( i , j ) such that the following four conditions are all satisfied: the path from n
View Solution →Polynomial Division
Consider a sequence, c0, c1, . . . , cn-1 , and a polynomial of degree 1 defined as Q(x ) = a * x + b. You must perform q queries on the sequence, where each query is one of the following two types: 1 i x: Replace ci with x. 2 l r: Consider the polynomial and determine whether is divisible by over the field , where . In other words, check if there exists a polynomial with integer coefficie
View Solution →Costly Intervals
Given an array, your goal is to find, for each element, the largest subarray containing it whose cost is at least k. Specifically, let A = [A1, A2, . . . , An ] be an array of length n, and let be the subarray from index l to index r. Also, Let MAX( l, r ) be the largest number in Al. . . r. Let MIN( l, r ) be the smallest number in Al . . .r . Let OR( l , r ) be the bitwise OR of the
View Solution →The Strange Function
One of the most important skills a programmer needs to learn early on is the ability to pose a problem in an abstract way. This skill is important not just for researchers but also in applied fields like software engineering and web development. You are able to solve most of a problem, except for one last subproblem, which you have posed in an abstract way as follows: Given an array consisting
View Solution →Self-Driving Bus
Treeland is a country with n cities and n - 1 roads. There is exactly one path between any two cities. The ruler of Treeland wants to implement a self-driving bus system and asks tree-loving Alex to plan the bus routes. Alex decides that each route must contain a subset of connected cities; a subset of cities is connected if the following two conditions are true: There is a path between ever
View Solution →