PROBLEM LINK:
Practice
Contest: Division 2
Contest: Division 1
Author: Ildar Gainullin
Tester: Alexander Morozov
Editorialist: Aman Dwivedi
DIFFICULTY:
MEDIUM-HARD
PREREQUISITES:
Dynamic Programming, Inclusion-Exclusion Principle, Bitmasking
PROBLEM:
For each k between 0 and N−1 (inclusive), we need to find the number of permutations of length N with cost k. Cost is defined as the number of adjacent pairs which are divisible and the quotient lies in the given set.
QUICK EXPLANATION:
- Masking on first N/2 numbers is done for building Dynamic Programming states.
- DP states is represented as (x,y), representing the number of permutations of length x which has a masked cost y, where cost is defined as the number of adjacent pairs which are divisible and the quotient lies in the given set.
- DP state is calculated in order from 1 to N, every combination of masked is checked and the number of ways are added accordingly,
- Finally output the number of permutations of length N which has a cost k where k lies between 0 and N-1 (inclusive).
EXPLANATION:
The main ideas is to use Inclusion-Exclusion Principle to find for each number of chains, the number of ways to divide numbers 1,2,3....N into chains such that in each of them, the adjacent pairs are divisible and the quotient lies in the given set.
Let us try to visualize it with using with the sample case:
- Here we have N=5 and the given set is S=10001. Now the total number of the permutations will be N!.
- The total number of the permutations such that their cost is 1 can be calculated as follows, we will try to put (P_{i-1},P_{i}) consecutively such that P_{i} is divisible by P_{i}. Hence we will make (P_{i-1},P_{i}) as a packet and now the number of permutations such that (P_{i-1},P_{i}) occurs consecutive will be 4!.
- Hence the total number of permutations with cost 1 are 4!.
- Now we will exclude all the all the permutation which has cost 1. Then we will be able to find the number of permutations whose cost is 0, which is 5!-4!.
Claim: We claim that P_{i}/P_{i-1} is never equal to 1.
Proof
It is quite obvious as P is permutation and hence there will be no two such values which would be equal. Hence we say that the quotient is never equal to 1, which leads us to further observation that P_{i}/P_{i-1} \ge 2
Claim: We claim that P_{i-1} \le N/2.
Proof
From the previous inequality we see that:
P_{i}/P_{i-1} \ge 2P_{i}/2 \ge P_{i-1}The maximum value a permutation of length N is N. Hence the maximum value that P_{i} can take is N. That leads us to our claim:
P_{i-1} \le N/2
Now, lets move towards Dynamic Programming.
We can slightly re-frame our task to: Find the values of P_{i} and P_{i-1} such that they form a valid pair, where valid pairs means such that P_{i} is divisible by P_{i-1} and the quotient lies in the given set.
No lets create our DP as (N,mask), which is defined as follows:
DP(N,mask) is defined as number of permutation of length N which have valid pairs (P_{i},P_{i-1}), such that P_{i-1} belongs to mask. The x^{th} bit is set in mask when x=P_{i-1}.
DP[0][0]=1, because there is only 1 such permutation as this is empty mask.
Let’s proceed forward and we will try to find DP(N,mask). Suppose that we have DP(N-1,mask), which means the permutation of length N-1. Now in this permutation of length N-1, we will try to insert N and where we place N depends on the type of mask that we get.
Consider that we have some permutation where (x,y) occurs consecutively. Since we are inserting N between (x,y), it can affect the x in the following way:
- x was valid in permutation of length N-1 and is also valid in permutation of length N.
- x was valid in permutation of length N-1 and is now invalid in permutation of length N.
- x was invalid in permutation of length N-1 and is now valid in permutation of length N.
- x was invalid in permutation of length N-1 and is also invalid in permutation of length N.
Let us see how these four types of masks effects the value of DP(N,mask).
Now for each x (1 \le x \le N-1) after which N is inserted and we will try to check for every insertion how does it effect for the above cases.
Case 1
x was valid x is still valid.
Here N is inserted after x such that after insertion (x,N,y). Basically previously y/x belongs to the set and now N/x belongs to the set. So x is still valid. We can say that for DP(N-1,mask) and DP(N,mask) the mask remains same.
DP(N,mask)+=DP(N-1,mask)because the addition of N doesn’t make change in the mask.
Case 2
x was valid but x is not valid now.
Here N is inserted after x such that after insertion (x,N,y). Basically previously y/x belongs to the set and now N/x doesn’t belongs to the set or N is not divisible by x. So x is not valid anymore. So now we need to remove x from the mask.
Mask can be changed by using xor to unset the x^{th} bit, so now:
DP(N,mask ⊕ (1<<x))+=DP(N-1,mask)because the addition of N make change in the mask.
Case 3
x was invalid but x is valid now.
This case is just opposite of the Case 2. Here y/x doesn’t belongs to the set but now N/x belongs to the set. So x is now valid and we need to add x to the mask.
Mask can be changed by using or to set the x^{th} bit, so now:
DP(N,mask | (1<<x))+=DP(N-1,mask)because the addition of N make change in the mask.
Case 4
x was invalid and x is still invalid now.
This case is similar to the Case 1. Here y/x doesn’t belongs to the set and also N/x doesn’t belongs to the set. So x was invalid and is still invalid. We can say that for DP(N-1,mask) and DP(N,mask) the mask remains same.
DP(N,mask)+=DP(N-1,mask)because the addition of N doesn’t make change in the mask.
Finally, we can calculate the number of permutations whose cost equals to k, where k lies between 0 and N-1 (inclusive) by unmasking.
TIME COMPLEXITY:
For the transition of DP states we need to start from the permutation of length 1 to permutation of length N and while generating a new permutation of length x, we need to check whether x is divisible by the previous numbers. Hence, this thing requires O(N^{2}) complexity.
We only need to store the mask for first N/2 numbers and hence at max we need to iterate for only 2^{N/2}.
Hence the Time Complexity will be O(N^{2} * 2^{N/2}).
SOLUTIONS:
Setter's Solution
#include <cmath>
#include <functional>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>
using namespace std;
typedef long long ll;
#ifdef iq
mt19937 rnd(228);
#else
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif
const int mod = 998244353;
void add(int &a, int b) {
a += b;
if (a >= mod) a -= mod;
if (a < 0) a += mod;
}
int mul(int a, int b) {
return (a * (ll) b) % mod;
}
const int N = 50;
int comb[N][N];
int fact[N];
int main() {
#ifdef iq
freopen("a.in", "r", stdin);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
unordered_map <ll, int> dp;
int n;
cin >> n;
comb[0][0] = 1;
for (int i = 0; i<= n; i++) {
for (int j = 0; j <= n; j++) {
if (i) add(comb[i][j], comb[i - 1][j]);
if (i && j) add(comb[i][j], comb[i - 1][j - 1]);
}
}
fact[0] = 1;
for (int i = 1; i <= n; i++) fact[i] = mul(fact[i - 1], i);
string t;
cin >> t;
dp[0] = 1;
for (int i = 1; i <= n; i++) {
unordered_map <ll, int> ndp;
for (auto c : dp) {
add(ndp[c.first | (1ll << i)], c.second);
}
for (int j = 1; j <= i; j++) {
if (i % j == 0 && t[i / j - 1] == '1') {
ll sw = (1ll << j) ^ (1ll << i);
for (auto c : dp) {
if ((c.first >> j) & 1) {
add(ndp[c.first ^ sw], c.second);
}
}
}
}
dp = ndp;
}
vector <int> ret(n);
for (auto c : dp) {
int chains = __builtin_popcountll(c.first);
int k = n - chains;
add(ret[k], mul(c.second, fact[chains]));
}
for (int i = n - 1; i >= 0; i--) {
for (int j = 0; j < i; j++) {
add(ret[j], -mul(ret[i], comb[i][j]));
}
}
for (int i = 0; i < n; i++) {
cout << ret[i] << ' ';
}
cout << endl;
}
Editorialist Solution
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define repa(i,a,n) for(int i=a;i<=n;i++)
#define repb(i,a,n) for(int i=a;i>=n;i--)
#define trav(x,a) for(auto &x: a)
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x).size()
#define fst first
#define snd second
#define pb push_back
#define mp make_pair
#define vt vector
typedef long double ld;
typedef pair <int,int> pii;
typedef vector <int> vi;
typedef long long ll;
template<class A> void read(vt<A>& v);
template<class T> void read(T& x){
cin>>x;
}
void read(double &d){
string t;
read(t);
d=stod(t);
}
void read(long double &d){
string t;
read(t);
d=stold(t);
}
template<class H, class... T> void read(H &h, T&...t){
read(h);
read(t...);
}
template <class A> void read(vt<A> &x){
trav(a,x)
read(a);
}
string to_string(char c){
return string(1,c);
}
string to_string(bool b){
return b?"true":"false";
}
string to_string(const char* s){
return string(s);
}
string to_string(string s){
return string(s);
}
string to_string(vt<bool> v){
string res;
rep(i,sz(v)){
res+=char('0'+v[i]);
}
return res;
}
template<class T> string to_string(T v){
bool f=1;
string res;
trav(x,v){
if(!f)
res+=' ';
f=0;
res+=to_string(x);
}
return res;
}
template<class A> void write(A x){
cout<<to_string(x);
}
template<class H, class...T> void write(const H& h, const T&...t){
write(h);
write(t...);
}
void print(){
write("\n");
}
template<class H, class...T> void print(const H& h, const T&...t){
write(h);
if(sizeof...(t))
write(' ');
print(t...);
}
/* -----------------------------------------------------------------------------------------------*/
const int mod=998244353;
const int len=2097155;
const int N=41;
int dp[N][len];
void add(int &x, int y){
x += y;
if(x>=mod)
x-=mod;
}
void pre(){
}
void solve(){
int n; read(n);
string s; read(s);
for(int i=0;i<=n;i++){
for(int j=0;j<len;j++){
dp[i][j]=0;
}
}
dp[0][0]=1;
for(int i=1;i<=n;i++){
int stop=i/2;
for(int mask=0;mask<(1<<(stop+1));mask++){
for(int j=0;j<i;j++){
if(j && (i%j==0) && s[i/j-1]=='1')
add(dp[i][mask|(1<<j)],dp[i-1][mask]);
else{
if(j>stop)
add(dp[i][mask],dp[i-1][mask]);
else
add(dp[i][(mask|(1<<j))^(1<<j)],dp[i-1][mask]);
}
}
}
}
vi ans(n);
for(int i=0;i<len;i++){
if(__builtin_popcount(i)<n)
add(ans[__builtin_popcount(i)],dp[n][i]);
}
print(ans);
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
pre();
int t=1;
// read(t);
rep(i,t) solve();
return 0;
}
, but one remark