PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Sahil Tiwari
Tester: Satyam, Utkarsh Gupta
Editorialist: Devendra Singh
DIFFICULTY:
To be calculated
PREREQUISITES:
PROBLEM:
Alice wants to test Bob’s love for the number 7.
Alice gives Bob a sequence of integers A = [A_1, A_2, \ldots, A_N], and Q queries. In each query, she provides an integer K and asks bob to find the number of lovely subsequences of size K that can be formed from A.
A sequence B of length K is called lovely if, for every subsequence S of B, the following condition holds:
- If |S| is divisible by 7, then the sum of S should also be divisible by 7.
- If |S| is not divisible by 7, then the sum of S should also not be divisible by 7.
where |S| denotes the length of S.
Help Bob answer the queries. Since the answers can be very large, print them modulo 10^9 + 7.
Note: Two subsequences are considered distinct if the indices chosen to form them are distinct, even if their elements end up being the same. For example, A = [1, 1, 2, 2] has 4 subsequences of length 1 (two are [1] and two are [2]) and 6 subsequences of length 2.
EXPLANATION:
As we are concerned with only the remainder of the sum of numbers, for all index i from i=1 to N, replace each element of the array A by A_i%7 and keep the count of all elements in the new array. Let Cnt_i represent the count of i in the modified array A. No index i with A_i=0 can be a part of a lovely subsequence as the subsequence formed by taking only this element does follow the second condition.
Now, for K>7 all lovely subsequences consist of exaclty 1 distinct number from 1 to 6.
Proof
Let us suppose there exists a lovely subsequence of A with length >7 which contains at least 2 distinct numbers. Select a subsequence, from this lovely subsequence, of size 7 such that it contains at least 2 distinct numbers. The sum of this subsequence has to be divisible by 7 as this is a subsequence of size 7 of a lovely subsequence (first condition). Now, pick any element from the remaining element of the lovely subsequence and swap this with any element in the subsequence, we took, of size 7 which is not equal to it (which must exist as there are two distinct values in the subsequence) and this sum cannot be divisible by 7 now.
\therefore for K>7 any lovely subsequence contains no more than 1 distinct number.
For K >7 iterate on values from i=1 to 6 and add {Cnt_i \choose K} to the answer.
For K<=7 we can pre-calculate the answer for each value of K from 1 to 7. We have 6 values for each element of the subsequence and this generates a total of 6^1 +6^2 ......6^7 different combinations (Since only count of each value is important sort all the combinations later). Iterate on each combination and check whether it is a lovely subsequence. The actual total number of lovely subsequences comes out to be very less (102). Now, for each lovely subsequence find the number of ways in which it can be constructed from A.
Let C_i represent the count of i in a lovely subsequence of size \leq 7, then the total number of possible ways to construct this lovely subsequence from A is given by {\displaystyle \prod_{i=1}^{6} \small{Cnt_i \choose C_i}}
Add this to the answer for a particular size K (equal to the length of this lovely subsequence).
Pre-calculations can de done for binomial coefficients to avoid increasing the runtime of the solution.
For details of implementation, please refer to the solutions attached.
TIME COMPLEXITY:
O(N+Q) or for each test case.
SOLUTION:
Setter's Solution
// Code by Sahil Tiwari (still_me)
#include <bits/stdc++.h>
#define endl "\n"
#define int long long int
#define tt \
int TESTCASE; \
cin >> TESTCASE; \
while (TESTCASE--)
#define arrin(a, n) \
for (int INPUT = 0; INPUT < n; INPUT++) \
cin >> a[INPUT]
using namespace std;
const int mod = 1e9 + 7;
const int N = 1000001;
// array to store inverse of 1 to N
int factorialNumInverse[N + 1];
// array to precompute inverse of 1! to N!
int naturalNumInverse[N + 1];
// array to store factorial of first N numbers
int fact[N + 1];
// Function to precompute inverse of numbers
void InverseofNumber(int p)
{
naturalNumInverse[0] = naturalNumInverse[1] = 1;
for (int i = 2; i <= N; i++)
naturalNumInverse[i] = naturalNumInverse[p % i] * (p - p / i) % p;
}
// Function to precompute inverse of factorials
void InverseofFactorial(int p)
{
factorialNumInverse[0] = factorialNumInverse[1] = 1;
// precompute inverse of natural numbers
for (int i = 2; i <= N; i++)
factorialNumInverse[i] = (naturalNumInverse[i] * factorialNumInverse[i - 1]) % p;
}
// Function to calculate factorial of 1 to N
void factorial(int p)
{
fact[0] = 1;
// precompute factorials
for (int i = 1; i <= N; i++)
{
fact[i] = (fact[i - 1] * i) % p;
}
}
// Function to return nCr % p in O(1) time
int Binomial(int N, int R, int p)
{
// n C r = n!*inverse(r!)*inverse((n-r)!)
if (N < R)
return 0;
if (N == R)
return 1;
int ans = ((fact[N] * factorialNumInverse[R]) % p * factorialNumInverse[N - R]) % p;
return ans;
}
bool ifsum(vector<int> a, int j, int k, map<pair<int, int>, int> &b)
{
if (k == 0)
return 1;
if (k < 0)
return 0;
if (j == a.size())
return 0;
if (b.find({j, k}) != b.end())
return b[{j, k}];
return b[{j, k}] = ifsum(a, j + 1, k - a[j], b) || ifsum(a, j + 1, k, b);
}
void create(vector<int> a, vector<vector<int>> &b, int k)
{
if (k == 0)
{
map<pair<int, int>, int> c;
if (!(ifsum(a, 0, 7, c) || ifsum(a, 0, 14, c) || ifsum(a, 0, 21, c) || ifsum(a, 0, 28, c) || ifsum(a, 0, 35, c) || ifsum(a, 0, 42, c)))
b.push_back(a);
return;
}
for (int i = 1; i < 6; i++)
{
vector<int> c = a;
c.push_back(i);
create(c, b, k - 1);
}
}
int calc(vector<int> y, vector<int> x)
{
int ans = 1;
for (int i = 0; i < 7; i++)
{
ans = (ans * Binomial(x[i], y[i], mod)) % mod;
}
return ans;
}
vector<int> change(vector<int> a)
{
vector<int> y(7);
for (int i : a)
y[i]++;
return y;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int p = 1000000007;
InverseofNumber(p);
InverseofFactorial(p);
factorial(p);
vector<vector<int>> a;
for (int i = 1; i <= 5; i++)
{
vector<int> b;
create(b, a, i);
}
set<vector<int>> c;
for (vector<int> i : a)
{
vector<int> x = change(i);
c.insert(x);
}
tt
{
int n , q;
cin >> n >> q;
vector<int> x(7);
int temp;
for (int i = 0; i < n; i++)
{
cin >> temp;
x[temp % 7]++;
}
while (q--)
{
int k;
cin >> k;
int ans = 0;
if (k >= 6)
{
for (int i = 1; i < 7; i++)
ans = (ans + Binomial(x[i], k, mod)) % mod;
}
else
{
for (vector<int> i : c)
{
int t = accumulate(i.begin(), i.end(), 0LL);
if (t == k)
{
int xx = calc(i, x);
ans = (ans + xx) % mod;
}
}
}
cout << ans << endl;
}
}
cerr << "time taken : " << (float)clock() / CLOCKS_PER_SEC << " secs" << endl;
return 0;
}
Tester-1's Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#ifndef ONLINE_JUDGE
#define debug(x) cerr<<#x<<" "; _print(x); cerr<<nline;
#else
#define debug(x);
#endif
/*
------------------------Input Checker----------------------------------
*/
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
if(!(l <= x && x <= r))
{
cerr<<"hi\n";
cerr << l << ' ' << r << ' ' << x << '\n';
assert(1 == 0);
}
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
/*
------------------------Main code starts here----------------------------------
*/
const ll MOD=1e9+7;
vector<ll> readv(ll n,ll l,ll r){
vector<ll> a;
if(n==0){
return a;
}
ll x;
for(ll i=1;i<n;i++){
x=readIntSp(l,r);
a.push_back(x);
}
x=readIntLn(l,r);
a.push_back(x);
return a;
}
const ll MAX=500500;
vector<ll> fact(MAX+2,1),inv_fact(MAX+2,1);
ll binpow(ll a,ll b,ll MOD){
ll ans=1;
a%=MOD;
while(b){
if(b&1)
ans=(ans*a)%MOD;
b/=2;
a=(a*a)%MOD;
}
return ans;
}
ll inverse(ll a,ll MOD){
return binpow(a,MOD-2,MOD);
}
void precompute(ll MOD){
for(ll i=2;i<MAX;i++){
fact[i]=(fact[i-1]*i)%MOD;
}
inv_fact[MAX-1]=inverse(fact[MAX-1],MOD);
for(ll i=MAX-2;i>=0;i--){
inv_fact[i]=(inv_fact[i+1]*(i+1))%MOD;
}
}
ll nCr(ll a,ll b,ll MOD){
if((a<0)||(a<b)||(b<0))
return 0;
ll denom=(inv_fact[b]*inv_fact[a-b])%MOD;
return (denom*fact[a])%MOD;
}
#define pb push_back
ll sumn=0,sumq=0;
vector<ll> freq(10,0);
vector<ll> ans(MAX,0);
map<vector<ll>,ll> visited;
void debg(vector<ll> a){
for(auto i:a){
cerr<<i<<" ";
}
cerr<<"\n";
return;
}
ll till=0;
void calc(vector<ll> track,vector<vector<ll>> dp){
if(visited[track]){
return;
}
visited[track]=1;
till++;
ll n=track[7];
if(n>1){
for(ll i=0;i<7;i++){
if(track[i]==n){
return;
}
}
}
for(ll i=0;i<7;i++){
for(ll j=0;j<7;j++){
ll l=min(1LL,i%7),r=min(1LL,j%7);
dp[i][j]=min(dp[i][j],1LL);
if(l!=r){
if(dp[i][j]){
return;
}
}
}
}
ll now=1;
for(ll i=0;i<7;i++){
now=(now*nCr(freq[i],track[i],MOD))%MOD;
}
ans[track[7]]=(ans[track[7]]+now)%MOD;
for(ll i=0;i<7;i++){
if(track[i]==freq[i]){
continue;
}
auto atrack=track; auto adp=dp;
atrack[i]++;
for(ll j=0;j<7;j++){
for(ll k=0;k<7;k++){
adp[(j+1)%7][(k+i)%7]+=dp[j][k];
}
}
atrack[7]++;
calc(atrack,adp);
}
}
void solve(){
ll n,q; cin>>n>>q;
vector<ll> a(n);
for(auto &it:a){
cin>>it;
}
sumn+=n,sumq+=q;
for(ll i=0;i<=7;i++){
freq[i]=0;
}
for(auto it:a){
freq[it%7]++;
}
for(ll i=1;i<=n;i++){
ans[i]=0;
}
vector<ll> track(8,0);
vector<vector<ll>> dp(7,vector<ll>(7,0));
dp[0][0]=1;
visited.clear();
calc(track,dp);
while(q--){
ll k; cin>>k;
ll final=ans[k];
if(k==1){
k=n+7;
}
for(ll i=1;i<7;i++){
final=(final+nCr(freq[i],k,MOD))%MOD;
}
cout<<final<<"\n";
}
return;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
freopen("error.txt", "w", stderr);
#endif
ll test_cases; cin>>test_cases;
precompute(MOD);
while(test_cases--){
solve();
}
assert(getchar()==-1);
assert(sumn<=(1e5));
assert(sumq<=(1e5));
cerr<<till;
return 0;
}
Tester-2's Solution
//Utkarsh.25dec
#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define vl vector <ll>
#define all(c) (c).begin(),(c).end()
using namespace std;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll modInverse(ll a){return power(a,mod-2);}
const int N=500023;
bool vis[N];
vector <vector <int>> adj[N];
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(1 == 0);
}
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
int sumN=0,sumQ=0;
ll fact[N];
ll invfact[N];
ll inv[N];
int maxN=0,maxQ=0;
void factorialsComputation()
{
inv[0]=inv[1]=1;
fact[0]=fact[1]=1;
invfact[0]=invfact[1]=1;
for(int i=2;i<N;i++)
{
inv[i]=(inv[mod%i]*(mod-mod/i))%mod;
fact[i]=(fact[i-1]*i)%mod;
invfact[i]=(invfact[i-1]*inv[i])%mod;
}
}
ll ncr(ll n,ll r)
{
ll ans=fact[n]*invfact[r];
ans%=mod;
ans*=invfact[n-r];
ans%=mod;
return ans;
}
int smallqueries=0,bigqueries=0;
int zeroans=0;
ll maxAnssm=0,maxAnsbig=0;
int seven=0;
void solve()
{
int n=readInt(1,100000,' ');
int q=readInt(1,100000,'\n');
sumN+=n;
sumQ+=q;
maxN=max(maxN,n);
maxQ=max(maxQ,q);
assert(sumN<=100000);
assert(sumQ<=100000);
int cnt[10]={0};
for(int i=1;i<=n;i++)
{
int c;
if(i==n)
c=readInt(1,1000000000,'\n');
else
c=readInt(1,1000000000,' ');
c%=7;
cnt[c]++;
}
ll ans[10]={0};
for(int k=1;k<=min(n,6);k++)
{
for(auto v:adj[k])
{
int num[10]={0};
for(auto it:v)
num[it]++;
ll tmpans=1;
for(int i=0;i<7;i++)
{
if(num[i]>cnt[i])
tmpans=0;
tmpans*=(ncr(cnt[i],num[i]));
tmpans%=mod;
}
ans[k]+=tmpans;
ans[k]%=mod;
}
}
while(q--)
{
int k=readInt(1,n,'\n');
if(k<=6)
{
smallqueries++;
cout<<ans[k]<<'\n';
maxAnssm=max(maxAnssm,ans[k]);
continue;
}
bigqueries++;
if(k==7)
seven++;
ll ans=0;
for(int i=1;i<7;i++)
{
if(cnt[i]>=k)
ans+=ncr(cnt[i],k);
ans%=mod;
}
cout<<ans<<'\n';
maxAnsbig=max(maxAnsbig,ans);
if(ans==0)
zeroans++;
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL),cout.tie(NULL);
factorialsComputation();
for(int k=1;k<=6;k++)
{
for(int i=1;i<power(k+1,7);i++)
{
int tmp=i;
int num[10]={0};
int flag=1;
int taken=0;
for(int j=0;j<7;j++)
{
num[j]+=(tmp%(k+1));
taken+=num[j];
tmp/=(k+1);
}
if(taken!=k || num[0]>0)
flag=0;
if(flag==0)
continue;
vector <int> v;
for(int j=0;j<7;j++)
for(int c=1;c<=num[j];c++)
v.pb(j);
for(int j=1;j<(1<<k);j++)
{
int sum=0;
for(int indx=0;indx<k;indx++)
{
if((j&(1<<indx))!=0)
sum+=v[indx];
}
if((sum%7)==0)
{
flag=0;
break;
}
}
if(flag==0)
continue;
adj[k].pb(v);
}
}
int T=readInt(1,1000,'\n');
int tt=T;
while(T--)
solve();
assert(getchar()==-1);
cerr<<"SUCCESS\n";
cerr<<"Total Tests: "<<tt<<'\n';
cerr<<"Sum of N: "<<sumN<<'\n';
cerr<<"Sum of Q: "<<sumQ<<'\n';
cerr<<"Maximum N: "<<maxN<<'\n';
cerr<<"Maximum Q: "<<maxQ<<'\n';
cerr<<"Small Queries: "<<smallqueries<<'\n';
cerr<<"Big Queries: "<<bigqueries<<'\n';
cerr<<"Queries with k = 7: "<<seven<<'\n';
cerr<<"Answer is 0: "<<zeroans<<'\n';
cerr<<"Maximum Answer in small Queries: "<<maxAnssm<<'\n';
cerr<<"Maximum Answer in big Queries: "<<maxAnsbig<<'\n';
}
Editorialist's Solution
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define pb push_back
#define all(_obj) _obj.begin(), _obj.end()
#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
ll INF = 1e18;
const int N = 1e5 + 11, mod = 1e9 + 7;
ll max(ll a, ll b) { return ((a > b) ? a : b); }
ll min(ll a, ll b) { return ((a > b) ? b : a); }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll factorial[N], inverse_factorial[N], NumInverse[N];
set<vector<int>> all;
ll binomial_coefficient(int n, int k)
{
if (n < k)
return 0;
return factorial[n] * inverse_factorial[k] % mod * inverse_factorial[n - k] % mod;
}
void add(vector<int> &v)
{
for (int i = v.size() - 1; i >= 0; i--)
if (v[i] < 6)
{
v[i]++;
return;
}
else
v[i] = 1;
return;
}
void sol(void)
{
int n, q;
cin >> n >> q;
vll a(n);
int cnt[7];
memset(cnt, 0, sizeof(cnt));
for (int i = 0; i < n; i++)
{
cin >> a[i];
a[i] %= 7;
cnt[a[i]]++;
}
ll ansfor[8];
memset(ansfor, 0, sizeof(ansfor));
for (int k = 1; k <= 7; k++)
{
for (auto x : all)
{
if (x.size() != k)
continue;
ll calc = 1;
int temp[7];
memset(temp, 0, sizeof(temp));
for (auto y : x)
temp[y]++;
for (int i = 1; i <= 6; i++)
calc *= binomial_coefficient(cnt[i], temp[i]), calc %= mod;
ansfor[k] += calc;
ansfor[k] %= mod;
}
}
while (q--)
{
int k;
cin >> k;
ll ans = 0, calc;
if (k > 7)
{
for (int i = 1; i <= 6; i++)
ans += binomial_coefficient(cnt[i], k);
ans %= mod;
}
else
{
ans = ansfor[k];
}
cout << ans << '\n';
}
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
NumInverse[0] = NumInverse[1] = 1;
factorial[0] = factorial[1] = 1;
inverse_factorial[0] = inverse_factorial[1] = 1;
for (int i = 2; i < N; i++)
{
NumInverse[i] = NumInverse[mod % i] * (mod - mod / i) % mod;
factorial[i] = factorial[i - 1] * i % mod;
inverse_factorial[i] = (NumInverse[i] * inverse_factorial[i - 1]) % mod;
}
for (int sz = 1; sz <= 7; sz++)
{
vector<int> v(sz, 1), finalv(sz, 6);
while (true)
{
bool flag = true;
for (int i = 0; i < (1 << sz); i++)
{
int sum = 0, bitcount = 0;
for (int j = 0; j < sz; j++)
if (i & (1 << j))
sum += v[j], bitcount++;
if ((sum % 7 == 0 && bitcount % 7 != 0) || (sum % 7 != 0 && bitcount % 7 == 0))
{
flag = false;
break;
}
}
if (flag)
{
vector<int> vv = v;
sort(all(vv));
all.insert(vv);
}
if (v == finalv)
break;
add(v);
}
}
int test = 1;
cin >> test;
while (test--)
sol();
}