CSES Mathematics Section Tutorial

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

So I did not find a tutorial for Maths section of CSES on codeforces, so thought of writing one.

I have put all my codes on https://github.com/div5252/CSES-Problem-Set.

This tutorial covers 29 questions of Mathematics Section of CSES.

1. Josephus Queries

Tutorial

Code

ll f(ll n,ll k)
{
    if(n==1) return 1;
    if(k<=(n+1)/2) 
    {
        if(2*k>n) return (2*k)%n;
        else return 2*k;
    }
    ll temp=f(n/2,k-(n+1)/2);
    if(n%2==1) return 2*temp+1;
    return 2*temp-1;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll q;
    cin>>q;
    for(int i=0;i<q;i++)
    {
        ll n,k;
        cin>>n>>k;
        cout<<f(n,k)<<"\n";
    }
}

2. Exponentiation

Tutorial

Code

const int MOD=1000000007;
long long int inverse(long long int i){
    if(i==1) return 1;
    return (MOD - ((MOD/i)*inverse(MOD%i))%MOD+MOD)%MOD;
}
ll POW(ll a,ll b)
{
    if(b==0) return 1;
    if(b==1) return a%MOD;
    ll temp=POW(a,b/2);
    if(b%2==0) return (temp*temp)%MOD;
    else return (((temp*temp)%MOD)*a)%MOD;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n,a,b;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a>>b;
        cout<<POW(a,b)<<"\n";
    }
}

3. Exponentiation II

Tutorial

Code

const int MOD=1000000007;
long long int inverse(long long int i){
    if(i==1) return 1;
    return (MOD - ((MOD/i)*inverse(MOD%i))%MOD+MOD)%MOD;
}
ll POW(ll a,ll b, ll mod)
{
    if(b==0) return 1;
    if(b==1) return a%mod;
    ll temp=POW(a,b/2,mod);
    if(b%2==0) return (temp*temp)%mod;
    else return (((temp*temp)%mod)*a)%mod;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n,a,b,c;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a>>b>>c;
        ll pw=POW(b,c,MOD-1);
        cout<<POW(a,pw,MOD)<<"\n";
    }
}

4. Counting Divisors

Tutorial

Code

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll d[1000005]={};
    for(int i=1;i<1000005;i++)
    {
        for(int j=i;j<1000005;j+=i)
        {
            d[j]++;
        }
    }
    ll n,x;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>x;
        cout<<d[x]<<"\n";
    }
}

5. Common Divisors

Tutorial

Code

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n;
    cin>>n;
    ll x[n];
    ll cnt[1000001]={};
    for(int i=0;i<n;i++)
    {
        cin>>x[i];
        cnt[x[i]]++;
    }
    for(int i=1000000;i>=1;i--)
    {
        ll d=0;
        for(int j=i;j<=1000000;j+=i) d+=cnt[j];
        if(d>=2)
        {
            cout<<i;
            return 0;
        }
    }
}

6. Sum of divisors

Tutorial

Code

const int MOD=1000000007;
long long int inverse(long long int i){
    if(i==1) return 1;
    return (MOD - ((MOD/i)*inverse(MOD%i))%MOD+MOD)%MOD;
}
ll POW(ll a,ll b)
{
    if(b==0) return 1;
    if(b==1) return a%MOD;
    ll temp=POW(a,b/2);
    if(b%2==0) return (temp*temp)%MOD;
    else return (((temp*temp)%MOD)*a)%MOD;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n;
    cin>>n;
    ll ans=0;
    for(ll i=1;i*i<=n;i++)
    {
        ans+=((n/i)*i)%MOD;
        ans%=MOD;
    }
    ll l=(ll)sqrt(n);
    for(ll i=sqrt(n);i>=1;i--)
    {
        ll r=n/i;
        ll sum=0;
        sum+=((((r%MOD)*((r+1)%MOD))%MOD)*inverse(2))%MOD;
        sum%=MOD;
        sum-=((((l%MOD)*((l+1)%MOD))%MOD)*inverse(2))%MOD;
        sum=(sum+MOD)%MOD;
        sum=(sum*i)%MOD;
        l=r;
        ans=(ans+sum)%MOD;
        //cout<<sum<<" ";
    }
    cout<<ans;
}

7. Divisor Analysis

Tutorial

Code

const int MOD=1000000007; 
const int MOD1=1000000006;
long long int inverse(long long int i, long long int mod){
    if(i==1) return 1;
    return (mod - ((mod/i)*inverse(mod%i,mod))%mod+mod)%mod;
}
ll POW(ll a,ll b)
{
    if(b==0) return 1;
    if(b==1) return a%MOD;
    ll temp=POW(a,b/2);
    if(b%2==0) return (temp*temp)%MOD;
    else return (((temp*temp)%MOD)*a)%MOD;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n;
    cin>>n;
    ll x[n],k[n];
    for(int i=0;i<n;i++)
    {
        cin>>x[i]>>k[i];
    }
    ll num=1;
    for(int i=0;i<n;i++)
    {
        num*=(k[i]+1)%MOD;
        num%=MOD;
    }
    ll sum=1;
    for(int i=0;i<n;i++)
    {
        ll temp=(POW(x[i],k[i]+1)+MOD-1)%MOD;
        temp*=inverse(x[i]-1,MOD);
        temp%=MOD;
        sum*=temp;
        sum%=MOD;
    }
    ll prod,num1=1;
    ll flag=0;
    for(int i=0;i<n;i++)
    {
        if(k[i]%2==1 && flag==0)
        {
            num1*=((k[i]+1)/2);
            num1%=MOD1;
            flag=1;
        }
        else
        {
            num1*=(k[i]+1)%MOD1;
            num1%=MOD1;
        }
    }
    if(flag==0)
    {
        for(int i=0;i<n;i++)
        {
            k[i]/=2;
        }
    }
    ll number=1;
    for(int i=0;i<n;i++)
    {
        number*=POW(x[i],k[i]);
        number%=MOD;
    }
    prod=POW(number,num1);
    cout<<num<<" "<<sum<<" "<<prod;
}

8. Prime Multiples

Tutorial

Code

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n,k;
    cin>>n>>k;
    ll a[k];
    for(int i=0;i<k;i++)
    {
        cin>>a[i];
    }
    ll ans=0;
    for(int i=0;i<(1ll<<k);i++)
    {
        vll v;
        for(int j=0;j<k;j++)
        {
            if((i&(1<<j))!=0)
            {
                v.PB(a[j]);
            }
        }
        ll prod=1;
        for(int j=0;j<v.size();j++)
        {
            if(prod>n/v[j])
            {
                prod=n+1;
                break;
            }
            prod*=v[j];
        }
        if(v.size()%2==0) ans-=n/prod;
        else ans+=n/prod;
    }
    ans+=n;
    cout<<ans;
}

9. Counting Coprime Pairs

Tutorial

Code

ll lpf[1000001],mobius[1000001];

void least_prime_factor()
{
    for(int i=2;i<1000001;i++)
    {
        if(!lpf[i])
        {
            for(int j=i;j<1000001;j+=i)
            {
                if(!lpf[j]) lpf[j]=i;
            }
        }
    }
}
 
void Mobius()
{
    for(int i=1;i<1000001;i++) 
    {
        if(i==1) mobius[i]=1;
        else 
        {
            if(lpf[i/lpf[i]]==lpf[i]) mobius[i]=0;
            else mobius[i]=-1*mobius[i/lpf[i]];
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n;
    cin>>n;
    ll x[n],cnt[1000001]={};
    for(int i=0;i<n;i++)
    {
        cin>>x[i];
        cnt[x[i]]++;
    }
    least_prime_factor();
    Mobius();
    ll ans=0;
    for(int i=1;i<1000001;i++)
    {
        if(mobius[i]==0) continue;
        ll d=0;
        for(int j=i;j<1000001;j+=i)
        {
            d+=cnt[j];
        }
        ans+=(d*(d-1))/2*mobius[i];
    }
    cout<<ans;
}

10. Binomial Coefficients

Tutorial

Code

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll fact[1000001];
    fact[0]=1;
    fact[1]=1;
    for(int i=2;i<=1000000;i++)
    {
        fact[i]=(fact[i-1]*i)%MOD;
    }
    ll n,a,b;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a>>b;
        ll ans=(fact[a]*inverse(fact[b]))%MOD;
        ans*=inverse(fact[a-b]);
        ans%=MOD;
        cout<<ans<<"\n";
    }
}

11. Creating Strings II

Tutorial

Code

const int MOD=1000000007;
long long int inverse(long long int i){
    if(i==1) return 1;
    return (MOD - ((MOD/i)*inverse(MOD%i))%MOD+MOD)%MOD;
}
ll POW(ll a,ll b)
{
    if(b==0) return 1;
    if(b==1) return a%MOD;
    ll temp=POW(a,b/2);
    if(b%2==0) return (temp*temp)%MOD;
    else return (((temp*temp)%MOD)*a)%MOD;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll fact[1000001];
    fact[0]=1;
    fact[1]=1;
    for(int i=2;i<=1000000;i++)
    {
        fact[i]=(fact[i-1]*i)%MOD;
    }
    string s;
    cin>>s;
    ll n=s.size();
    ll cnt[26]={};
    for(int i=0;i<n;i++)
    {
        cnt[s[i]-'a']++;
    }
    ll tot=fact[n];
    for(int i=0;i<26;i++)
    {
        tot*=inverse(fact[cnt[i]]);
        tot%=MOD;
    }
    cout<<tot;
}

12. Distributing Apples

Tutorial

Code

const int MOD=1000000007;
long long int inverse(long long int i){
    if(i==1) return 1;
    return (MOD - ((MOD/i)*inverse(MOD%i))%MOD+MOD)%MOD;
}
ll POW(ll a,ll b)
{
    if(b==0) return 1;
    if(b==1) return a%MOD;
    ll temp=POW(a,b/2);
    if(b%2==0) return (temp*temp)%MOD;
    else return (((temp*temp)%MOD)*a)%MOD;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll fact[2000001];
    fact[0]=1;
    fact[1]=1;
    for(int i=2;i<=2000000;i++)
    {
        fact[i]=(fact[i-1]*i)%MOD;
    }
    ll n,m;
    cin>>n>>m;
    ll ans=(fact[m+n-1]*inverse(fact[n-1]))%MOD;
    ans*=inverse(fact[m]);
    ans%=MOD;
    cout<<ans;
}

13. Christmas Party

Tutorial

Code

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n;
    cin>>n;
    ll d[n+1];
    d[1]=0;
    d[2]=1;
    for(ll i=3;i<=n;i++)
    {
        d[i]=(((d[i-1]+d[i-2])%MOD)*(i-1))%MOD;
    }
    cout<<d[n];
}

14. Bracket Sequences I

Tutorial

Code

const int MOD=1000000007; 
long long int inverse(long long int i){
    if(i==1) return 1;
    return (MOD - ((MOD/i)*inverse(MOD%i))%MOD+MOD)%MOD;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n;
    cin>>n;
    if(n%2==1) 
    {
        cout<<0;
        return 0;
    }
    n/=2;
    ll fact[2*n+1];
    fact[0]=1;
    for(ll i=1;i<=2*n;i++)
    {
        fact[i]=(fact[i-1]*i)%MOD;
    }
    ll ans=(fact[2*n]*inverse(fact[n]))%MOD;
    ans*=(inverse(fact[n])*inverse(n+1))%MOD;
    ans%=MOD;
    cout<<ans;
}

15. Bracket Sequences II

Tutorial

Code

const int MOD=1000000007;
long long int inverse(long long int i){
    if(i==1) return 1;
    return (MOD - ((MOD/i)*inverse(MOD%i))%MOD+MOD)%MOD;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n;
    cin>>n;
    if(n%2==1)
    {
        cout<<0;
        return 0;
    }
    n/=2;
    string s;
    cin>>s;
    ll k=0,o=0;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]=='(') 
        {
            k++;
            o++;
        }
        else k--;
        if(k<0)
        {
            cout<<0;
            return 0;
        }
    }
    n-=o;
    if(k<0 || n<0 || 2*n+k<n)
    {
        cout<<0;
        return 0;
    }
    ll fact[2*n+k+1];
    fact[0]=1;
    for(int i=1;i<=2*n+k;i++)
    {
        fact[i]=(fact[i-1]*i)%MOD;
    }
    ll ans=(fact[2*n+k]*inverse(fact[n]))%MOD;
    ans*=inverse(fact[n+k]);
    ans%=MOD;
    ans*=((k+1)*inverse(n+k+1))%MOD;
    ans%=MOD;
    cout<<ans;
}

16. Counting Necklaces

Tutorial

Code

const int MOD=1000000007; 
long long int inverse(long long int i){
    if(i==1) return 1;
    return (MOD - ((MOD/i)*inverse(MOD%i))%MOD+MOD)%MOD;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n,m;
    cin>>n>>m;
    ll ans=0;
    for(ll i=0;i<n;i++)
    {
        ll temp=POW(m,__gcd(i,n));
        temp*=inverse(n);
        temp%=MOD;
        ans+=temp;
        ans%=MOD;
    }
    cout<<ans;
}

17. Counting Grids

18. Fibonacci Numbers

Tutorial

Code

const int MOD=1000000007;
long long int inverse(long long int i){
    if(i==1) return 1;
    return (MOD - ((MOD/i)*inverse(MOD%i))%MOD+MOD)%MOD;
}
ll POW(ll a,ll b)
{
    if(b==0) return 1;
    if(b==1) return a%MOD;
    ll temp=POW(a,b/2);
    if(b%2==0) return (temp*temp)%MOD;
    else return (((temp*temp)%MOD)*a)%MOD;
}
map<ll,ll> f;

ll fib(ll n)
{
    if(f.count(n)) return f[n];
    if(n==0) return 0;
    if(n==1 || n==2) return 1;
    if(n%2==0)
    {
        ll k=n/2;
        ll ret1=fib(k-1),ret2=fib(k);
        return f[n]=((((2ll*ret1)%MOD+ret2)%MOD)*ret2)%MOD;
    }
    else
    {
        ll k=(n+1)/2;
        ll ret1=fib(k-1),ret2=fib(k);
        return f[n]=( (ret1*ret1)%MOD + (ret2*ret2)%MOD)%MOD;
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n;
    cin>>n;
    cout<<fib(n);
}

19. Throwing Dice

Tutorial

Code

const int MOD=1000000007;
long long int inverse(long long int i){
    if(i==1) return 1;
    return (MOD - ((MOD/i)*inverse(MOD%i))%MOD+MOD)%MOD;
}
ll POW(ll a,ll b)
{
    if(b==0) return 1;
    if(b==1) return a%MOD;
    ll temp=POW(a,b/2);
    if(b%2==0) return (temp*temp)%MOD;
    else return (((temp*temp)%MOD)*a)%MOD;
}

vector<vll> mul(vector<vll> x, vector<vll> y) {
    vector<vll> r(6, vll(6));
    for (int j = 0; j < 6; j++)
    {
        for (int k = 0; k < 6; k++) 
        {
            for (int l = 0; l < 6; l++)
            {
                r[j][k] = (r[j][k]+(x[j][l]*y[l][k])%MOD)%MOD;
            }
        }
    }
    return r;
}

vector<vll> modpow(vector<vll> x, ll n) 
{
    if (n == 0)
    {
        vector<vll> r(6, vll(6));
        for (int i = 0; i < 6; i++) r[i][i] = 1;
        return r;
    }
    vector<vll> u = modpow(x, n/2);
    u = mul(u, u);
    if (n%2==1) u = mul(u, x);
    return u;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n;
    cin>>n;
    vector<vll> a(6,vll(6));
    for(int i=0;i<5;i++)
    {
        a[i][i+1]=1;
    }
    for(int i=0;i<6;i++)
    {
        a[5][i]=1;
    }
    vector<vll> ans=modpow(a,n);
    cout<<ans[5][5];
}

20. Graph Paths I

Tutorial

Code

const int MOD=1000000007;
long long int inverse(long long int i){
    if(i==1) return 1;
    return (MOD - ((MOD/i)*inverse(MOD%i))%MOD+MOD)%MOD;
}
ll POW(ll a,ll b)
{
    if(b==0) return 1;
    if(b==1) return a%MOD;
    ll temp=POW(a,b/2);
    if(b%2==0) return (temp*temp)%MOD;
    else return (((temp*temp)%MOD)*a)%MOD;
}

ll n;

vector<vll> mul(vector<vll> x, vector<vll> y) {
    vector<vll> r(n, vll(n));
    for (int j = 0; j < n; j++)
    {
        for (int k = 0; k < n; k++) 
        {
            for (int l = 0; l < n; l++)
            {
                r[j][k] = (r[j][k]+(x[j][l]*y[l][k])%MOD)%MOD;
            }
        }
    }
    return r;
}

vector<vll> modpow(vector<vll> x, ll pw) 
{
    if (pw == 0)
    {
        vector<vll> r(n, vll(n));
        for (int i = 0; i < n; i++) r[i][i] = 1;
        return r;
    }
    vector<vll> u = modpow(x, pw/2);
    u = mul(u, u);
    if (pw%2==1) u = mul(u, x);
    return u;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll m,k,a,b;
    cin>>n>>m>>k;
    vector<vll> v(n,vll (n,0));
    for(int i=0;i<m;i++)
    {
        cin>>a>>b;
        a--; b--;
        v[a][b]++;
    }
    cout<<modpow(v,k)[0][n-1];
}

21. Graph Paths II

Tutorial

Code

const int MOD=1000000007;
long long int inverse(long long int i){
    if(i==1) return 1;
    return (MOD - ((MOD/i)*inverse(MOD%i))%MOD+MOD)%MOD;
}
ll POW(ll a,ll b)
{
    if(b==0) return 1;
    if(b==1) return a%MOD;
    ll temp=POW(a,b/2);
    if(b%2==0) return (temp*temp)%MOD;
    else return (((temp*temp)%MOD)*a)%MOD;
}

ll INF=4e18;
ll n;

vector<vll> mul(vector<vll> x, vector<vll> y) {
    vector<vll> r(n, vll(n,INF));
    for (int j = 0; j < n; j++)
    {
        for (int k = 0; k < n; k++) 
        {
            for (int l = 0; l < n; l++)
            {
                r[j][k] = min(r[j][k],x[j][l]+y[l][k]);
            }
        }
    }
    return r;
}

vector<vll> modpow(vector<vll> x, ll pw) 
{
    if (pw == 1)
    {
        return x;
    }
    vector<vll> u = modpow(x, pw/2);
    u = mul(u, u);
    if (pw%2==1) u = mul(u, x);
    return u;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll m,k,a,b,c;
    cin>>n>>m>>k;
    vector<vll> v(n,vll(n,INF));
    for(int i=0;i<m;i++)
    {
        cin>>a>>b>>c;
        a--; b--;
        v[a][b]=min(v[a][b],c);
    }
    ll ans=modpow(v,k)[0][n-1];
    if(ans==INF) cout<<"-1";
    else cout<<ans;
}

22. Dice Probability

Tutorial

Code

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n,a,b;
    cin>>n>>a>>b;
    vector<vector<ld> > dp(n+1,vector<ld> (6*n+1,0));
    dp[0][0]=1.0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=6*n;j++)
        {
            for(int k=1;k<=6;k++)
            {
                if(j-k>=0)
                {
                    dp[i][j]+=dp[i-1][j-k];
                }
            }
            dp[i][j]=dp[i][j]/6;
        }
    }
    ld ans=0;
    for(int i=a;i<=b;i++)
    {
        ans+=dp[n][i];
    }
    ans*=1e6;
    ans=llround(ans);
    ans/=1e6;
    cout<<fixed<<setprecision(6)<<ans;
}

23. Moving Robots

Tutorial

Code

ll dr[4]={1,-1,0,0};
ll dc[4]={0,0,1,-1};

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n;
    cin>>n;
    ld dp[n+1][8][8]={};
    ld ans[8][8];
    for(int i=0;i<8;i++)
    {
        for(int j=0;j<8;j++)
        {
            ans[i][j]=1;
        }
    }
    for(int i=0;i<8;i++)
    {
        for(int j=0;j<8;j++)
        {
            for(int k=0;k<=n;k++)
            {
                for(int i1=0;i1<8;i1++)
                {
                    for(int j1=0;j1<8;j1++)
                    {
                        dp[k][i1][j1]=0;
                    }
                }
            }
            dp[0][i][j]=1;
            for(int k=0;k<n;k++)
            {
                for(int i1=0;i1<8;i1++)
                {
                    for(int j1=0;j1<8;j1++)
                    {
                        ld dir=0;
                        for(int f=0;f<4;f++)
                        {
                            ll u=i1+dr[f],v=j1+dc[f];
                            if(u>=0 && u<8 && v>=0 && v<8)
                            {
                                dir++;
                            }
                        }
                        for(int f=0;f<4;f++)
                        {
                            ll u=i1+dr[f],v=j1+dc[f];
                            if(u>=0 && u<8 && v>=0 && v<8)
                            {
                                dp[k+1][u][v]+=dp[k][i1][j1]/dir;
                            }
                        }
                    }
                }
            }
            for(int i1=0;i1<8;i1++)
            {
                for(int j1=0;j1<8;j1++)
                {
                    ans[i1][j1]*=(1-dp[n][i1][j1]);
                }
            }
        }
    }
    ld expc=0;
    for(int i=0;i<8;i++)
    {
        for(int j=0;j<8;j++)
        {
            expc+=ans[i][j];
        }
    }
    cout<<fixed<<setprecision(6)<<expc;
}

24. Candy Lottery

Tutorial

Code

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n,k;
    cin>>n>>k;
    ld ans=0;
    for(int i=1;i<=k;i++)
    {
        ld add=1,sub=1;
        for(int j=1;j<=n;j++)
        {
            add*=(ld)i/(ld)k;
            sub*=(ld)(i-1)/(ld)k;
        }
        ans+=(ld)(i)*(ld)(add-sub);
    }
    ans*=1e6;
    ans=llround(ans);
    ans/=1e6;
    cout<<fixed<<setprecision(6)<<ans;
}

25. Inversion Probability

Tutorial

Code

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n;
    cin>>n;
    ll a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    ld ans=0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<i;j++)
        {
            ll k;
            if(a[j]<=a[i])
            {
                k=(a[j]*(a[j]-1))/2;
            }
            else
            {
                k=(a[i]*(a[i]-1))/2 + (a[j]-a[i])*a[i];
            }
            ans+=(ld)k/(ld)(a[j]*a[i]);
        }
    }
    cout<<fixed<<setprecision(6)<<ans;
}

26. Stick Game

Tutorial

Code

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n,k;
    cin>>n>>k;
    ll p[k];
    for(int i=0;i<k;i++)
    {
        cin>>p[i];
    }
    ll dp[n+1]={};
    dp[0]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<k;j++)
        {
            if(i-p[j]>=0 && dp[i-p[j]]==0)
            {
                dp[i]=1;
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(dp[i]==1) cout<<"W";
        else cout<<"L";
    }
}

27. Nim Game I

Tutorial

Code

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll t,n;
    cin>>t;
    for(int i=0;i<t;i++)
    {
        cin>>n;
        ll x[n];
        ll xr=0;
        for(int i=0;i<n;i++)
        {
            cin>>x[i];
            xr^=x[i];
        }
        if(xr!=0) cout<<"first";
        else cout<<"second";
        cout<<"\n";
    }
}

28. Nim Game II

Tutorial

Code

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll t,n;
    cin>>t;
    for(int i=0;i<t;i++)
    {
        cin>>n;
        ll x[n];
        ll xr=0;
        for(int i=0;i<n;i++)
        {
            cin>>x[i];
            x[i]%=4;
            xr^=x[i];
        }
        if(xr!=0) cout<<"first";
        else cout<<"second";
        cout<<"\n";
    }
}

29. Stair Game

Tutorial

Code

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll t,n;
    cin>>t;
    for(int i=0;i<t;i++)
    {
        cin>>n;
        ll a[n];
        ll xr=0;
        for(int i=0;i<n;i++)
        {
            cin>>a[i];
            if(i%2)
            {
                xr^=a[i];
            }
        }
        if(xr) cout<<"first";
        else cout<<"second";
        cout<<"\n";
    }
}

30. Grundy's Game

Tutorial

Code

ll mex(vll v)
{
    set<ll> s;
    for(int i=0;i<v.size();i++)
    {
        s.insert(v[i]);
    }
    for(int i=0;i<1000001;i++)
    {
        if(s.count(i)==0) return i;
    }
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll limit=2000;
    ll dp[limit];
    dp[0]=dp[1]=dp[2]=0;
    for(int i=3;i<limit;i++)
    {
        vll v;
        for(int j=1;2*j<i;j++)
        {
            v.PB(dp[j]^dp[i-j]);
        }
        dp[i]=mex(v);
    }
    ll t;
    cin>>t;
    for(int i=0;i<t;i++)
    {
        ll n;
        cin>>n;
        if(n>=limit) cout<<"first";
        else if(dp[n]==0) cout<<"second";
        else cout<<"first";
        cout<<"\n";
    }
}

31. Another Game

UPD: I have also added tutorials for the newly added problems in Maths section. I am yet to do two problems — Counting Grids and Another Game. It would be helpful if someone could come up with tutorials for these.

Comments (54)

Show archived | Write comment?

sahal

4 years ago, # |

Thanks man...

→ Reply

agayush

Thanks a lot!

divyamsingal01

UPD: The tutorial is now complete. I have put the explanations and codes for all 21 problems.

If you find any typo or any improvement in the explanation, please comment below.

I haven't put the complete code(template portion) in the tutorial above, so as to prevent people for directly copying. Still if you wish to see the complete code, I have to the link to my github which contains AC solutions.

snorkel

I still do not get sum of divisors :(

navneet.h

4 years ago, # ^ |

← Rev. 2 →

link this might help, see the last answer

Yeah sorry, I have updated the explanation. I hope it is clear now.

Invaders

Thanks

hydra_cody

2 years ago, # ^ |

https://www.geeksforgeeks.org/sum-divisors-1-n/

decoder__

← Rev. 3 →

divyamsingal01 can you share the links to the editorials of other sections if you have found them?

Range queries https://mirror.codeforces.com/blog/entry/77128
Graph https://mirror.codeforces.com/blog/entry/79518
DP https://mirror.codeforces.com/blog/entry/70018

Shameek

← Rev. 4 →

can you please verify if i understood moving robots correctly —

for each robot we first get what is the probability for it to be on some i, j cell after k iterations.

then for each cell what is the probability that it was empty after k iterns? — probability that robot 1 isnt there * probability that robot 2 isnt there and so on.... so we multiply the 1 — dp[i1][j1]

now expectation — sum(P(xi)*xi) we calculated P(xi) and xi is 1?

nor

For 21, here's a fairly straightforward proof:

This game is essentially equivalent to Nim with a restricted number of additions permitted, with the piles being on the even indices, and the permitted additions being precisely the ones which can be done due to the shift from the pile on the immediate right (if it exists), with the only other possible move being removal of one element from an even pile at most a finite number of times, and thus this game is equivalent to vanilla Nim (proof here: https://cp-algorithms.com/game_theory/sprague-grundy-nim.html#toc-tgt-5), from where it is obvious.

RisingWizard

In Graph Paths II, how did you decide the value of INF?

I took INF=7e18 and it was giving WA, but on changing it to 4e18, it got Accepted!

RonSkk23

You might be having long long overflow due to 7e18. Initialize, it sufficiently large so that it serves its purpose and encounters no overflow scenario.

tourist9

Mathematical Proof for Q21. It is a Staircase Nim Problem and can be easily proven that only even position value affects our answer. For the proof click here

spookywooky

Counting Necklaces How to get the inclusion/exclusion right?

Can sombody explain with example n=12?

fischerman

It's not that trivial if you don't know group theory, try reading about burnside's lemma.

Found this which gives basically the solution. Link

If you would like to solve a similar problem on this theory , you may try this one https://mirror.codeforces.com/gym/101873/problem/B

arnab_baishnab

21 month(s) ago, # ^ |

← Rev. 6 →

div[i] is ith divisor of n. dp[y] is actual correct answer patterns of length y only.

(i) let us solve the same problem for each divisor of n.
(ii) x=div[i]. res = pow(m,x). (which is yet not correct.)
(iii) we have overcounted the results of divisors of x.
(iv) for each divisors of x we have to do res-=dp[y]*y. ( where y is divisor of x. dp[y]*y because total y rotoations possible)
(v) now our "res" is almost fine but it contains the rotations of x. so we have to divide "res" by "x". now res is ready to be stored in dp array . so dp[x] = res .
(vi) final answer for n is sum of all res of all divisors of n.

why we are concerned with divisors?? any pattern can complete it's cycle iff it's length divides n. here's ac code

Sindy

anyone solved grundy's game ?

nikhil_vaibhav_17

3 years ago, # |

In exponentiation II , why we use fermat's theorem ? Can't we just find x = power(b,c) and then power(a,x) ? I tried but it didn't work. So I want to know why? Note : I am not from Maths background so if you will share any resources it will be very useful.

3 years ago, # ^ |

That's because $$$b^c$$$ will overflow (doesn't fit in long long), so we used Fermat's Theorem.

cpdantes

Hi In COUNTING DIVISORS (problem-4), I understand that an array of 0s is created and then each 0 in the array is incremented in the for-loops.

I want to know the rationale behind this. Why this works?

nikhil1_raghav

Explained it here

Letscode_sundar

The program given there and even mine gives RE and TLE (at times) when i am executing.

What's wrong in the code given there?

Not mentioned in the snippet but value of $$$N$$$ is $$$10^6+1$$$. That could be the reason for RE.

Thienu

For Another Game, the first player wins iff there is at least one heap with an odd number of coins.

If all heaps have an even number of coins, the second player can win, by taking coins from the same set of piles as the first player on the previous turn. This ensures that all heaps have an even number of piles at the end of the second player's turn, so the strategy can continue.

If at least one heap has an odd number of coins, the first player can win by taking one coin from each pile with an odd number of coins, reducing the game to the first scenario.

Proof of Stair Game is as follows:

Consider the nim game on the even-numbered piles. If the first player wins this game, they can win the entire game. A valid strategy:

In the first move, play in the even-numbered piles with an optimal nim strategy.

In subsequent moves:

If the second player moves coins from an odd-numbered pile $$$p$$$ to pile $$$p-1$$$, the first player should move the same number of coins from $$$p-1$$$ to $$$p-2$$$. Note that the nim game on the even-numbered piles is unaffected, and it is impossible for the first player to lose during this.
If the second player moves coins from an even-numbered pile, they have effectively made a move in the nim game, so the first player's next move should be to play an optimal move in the nim game.

After all the moves in the nim game have been exhausted, we know that the second player has the next move and that all coins are in odd-numbered piles, which means the first player ultimately wins using this strategy.

If the second player wins the nim game, use a similar strategy as the one above (i.e. if first player plays on odd-numbered pile, mirror their move; if they play on even-numbered pile, play nim game).

chuka231

Thanks!

https://math.stackexchange.com/questions/3587286/using-group-actions-to-determine-the-different-colourings-of-a-grid

dutin


#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
const ll MOD = 1e9 + 7;
 
ll fast_pow(ll a, ll b) { 
    ll res = 1; 
    for (a %= MOD; b; b >>= 1) { 
        if (b & 1) 
            res = res * a % MOD; 
        a = a * a % MOD; 
    } 
    return res; 
}
 
ll N;
 
int main() { 
    cin >> N;
    ll a = fast_pow(2, N * N);
    ll b = (N % 2 == 0 ? fast_pow(2, N * N / 4) : fast_pow(2, (N * N - 1) / 4) * 2 % MOD);
    ll c = (N % 2 == 0 ? fast_pow(2, N * N / 2) : fast_pow(2, N * (N - 1) / 2) * fast_pow(2, N / 2 + 1) % MOD);
    ll d = b;
 
    cout << (a + b + c + d) % MOD * 250000002 % MOD << '\n';
}

(Sorry for the Necropost)

2002002

in case someone is wondering how to get $$$250000002$$$ without using online calculator

#include <bits/stdc++.h>
using namespace std;

int extended_euclidean(int a, int b, int &x, int &y) {
	if(a == 0) {
		x = 0, y = 1;
		return b;
	}
	int x1, y1, d = extended_euclidean(b % a, a, x1, y1);
	x = y1 - (b / a) * x1, y = x1;
	return d;
}
 
int modular_inverse(int a, int m) {
	int x, y;
	int g = extended_euclidean(a, m, x, y);
	if (g != 1) return -1;
	else {
		x = (x % m + m) % m;
		return x;
	}
}

long long mod_pow(long long base, long long exp, long long mod) {
	long long res = 1;
	while (exp > 0) {
		if (exp & 1) res = (res * base) % mod;
			base = (base * base) % mod;
			exp >>= 1;
		}
	return res;
}

const int M = 1e9 + 7;
const int G = 4;

void solve() {
	long long N; cin >> N;
	long long deg0   = mod_pow(2, N * N, M);
	long long deg90  = (N & 1 ? mod_pow(2, (N * N - 1) / 4, M) * 2 : 
				    mod_pow(2, N * N / 4, M)) % M;
	long long deg180 = (N & 1 ? mod_pow(2, (N * N - 1) / 2, M) * 2 : 
				    mod_pow(2, N * N / 2, M)) % M;
	long long deg270 = deg90;
	long long ans = (deg0 + deg90 + deg180 + deg270) % M;
	(ans *= modular_inverse(G, M)) %= M;
	cout << ans << endl;
}
 
int main() {
	ios_base::sync_with_stdio(false), cin.tie(nullptr);
 
 	// int T; cin >> T;
 	// while(T--) solve();
 	solve();
	return 0;
}

Wolfram Alpha works perfectly well

Wayne_Yan

for stair game, the proof is as follows:

say player A ( let it be first or second ) have winning strategy in the nim game you considered, how can A still have a winning strategy in the original game?

the new strategy is simple, when player B moves n coins from an odd-numbered stair k, A moves the same amount of coins from stair k-1 to k-2, this preserves the nim game; when B's move is on an even numbered stair, we proceed with our original strategy.

the way I found this property is through testing some possibilities for n = 1,2,3,4,5. Hope this helps!

catalystgma

Another proof for Another Game:

$$$\lbrace 1 \rbrace$$$ is winning for you, just take the coin.
$$$\lbrace 2 \rbrace$$$ is losing, because you can only take one coin, leading to $$${1}$$$ for your opponent, which is winning.
$$$\lbrace \rbrace$$$ is losing, there are no moves to be done.

Let $$$E_{i,j}$$$ be a set which contains the multisets of any $$$i$$$ even nonzero numbers ($$$i \ge 1$$$), with their sum $$$j$$$ ($$$j \ge 2i$$$).

Also, let $$$E_{i,0} = \lbrace\lbrace\rbrace\rbrace$$$ for any $$$i \ge 1 \Rightarrow E_{i,0}$$$ contains only losing multisets for any $$$i \ge 1$$$.

(Induction A)

If $$$E_{1,j}$$$ (any $$$j \ge 2$$$), $$$E_{2,j}$$$ (any $$$j \ge 4$$$), .., $$$E_{i-1,j}$$$ (any $$$j \ge 2i-2$$$) all contain only losing multisets, we will prove by induction that $$$E_{i,2i}$$$ also contains only losing multisets.

$$$E_{i,2i}$$$ is only formed from the multiset $$$\lbrace 2, 2, 2, .., 2 \rbrace$$$ (i times)

Any move we will do will lead to $$$\lbrace 2, 2, .., 2 \rbrace$$$ (i-k times) ∪ $$$\lbrace 1, 1, 1, .., 1 \rbrace$$$ (k times) | $$$1 \le k \le i$$$

Our opponent will mimic our move, leading to:

$$$\lbrace 2, 2, .., 2 \rbrace$$$ (i-k times) $$$\in E_{i-k,2i-2k}$$$ , which we already claimed it is losing.

(Induction B)

If $$$E_{1,j}$$$ (any $$$j \ge 2$$$), $$$E_{2,j}$$$ (any $$$j \ge 4$$$), .., $$$E_{i-1,j}$$$ (any $$$j \ge 2i-2$$$), $$$E_{i,2i}$$$, $$$E_{i,2i+2}$$$, .., $$$E_{i,2k-2}$$$ all contain only losing multisets, we will prove by induction that $$$E_{i,2k}$$$ also contains only losing multisets.

Let $$$E \in E_{i,2k}$$$, $$$E = \lbrace e_1, e_2, .., e_i | e_1 + e_2 + .. + e_i = 2k \rbrace$$$

Any move we will do will lead to the following split of $$$\lbrace e_1, e_2, .., e_i \rbrace$$$: $$$\lbrace e_{a_{1}}, e_{a_{2}}, .., e_{a_{x}}} ∪ {e_{b_{1}}-1, e_{b_{2}}-1, .., e_{b_{y}}-1 \rbrace$$$ with $$$\lbrace a_1, a_2, .., a_x \rbrace ∪ \lbrace b_1, b_2, .., b_y \rbrace = \lbrace 1, 2, .., i \rbrace, x + y = i$$$.

Our opponent will mimic our move, leading to: $$$\lbrace e_{a_{1}}, e_{a_{2}}, .., e_{a_{x}}} ∪ {e_{b_{1}} - 2, e_{b_{2}} - 2, .., e_{b_{y}} - 2 \rbrace$$$, which $$$\in E_{i,2k-2y}$$$, which we have already claimed to be losing; since it is again our move, $$$E$$$ is losing.

Since $$$E_{1,2} = \lbrace\lbrace 2 \rbrace\rbrace \Leftrightarrow E_{1,2}$$$ contains only losing multisets, by applying (Induction B) (we can apply it, $$$\lbrace\rbrace$$$ is losing) $$$\Rightarrow E_{1,4}$$$, $$$E_{1,6}$$$, $$$E_{1,8}$$$, ... all contain only losing multisets.

So $$$E_{1,j}$$$ (any $$$j \ge 2$$$) contains only losing multisets. Now we apply (Induction A) $$$\Rightarrow$$$ $$$E_{2,4}$$$ contains only losing multisets.

We now apply (Induction B) again $$$\Rightarrow E_{2,6}$$$, $$$E_{2,8}$$$, $$$E_{2,10}$$$, ... all contain only losing multisets.

...

By continuing to repeatedly swap between (Induction B) and (Induction A), we can conclude that $$$E_{i,j}$$$ (any $$$i \ge 1$$$, any $$$j \ge 2i$$$) contains only losing multisets.

In other words, any multiset that contains only even numbers is losing.

If we start with even numbers only, we lose. Otherwise, during our first turn we will subtract $$$1$$$ only from the odd numbers we have, leaving our opponent with a losing configuration of even numbers only.

rsvns

2 years ago, # |

Can anyone explain me Q.2 Why to do "mod-1" for b^c ?

Qualified

Euler's theorem states that if $$$\gcd(a, c)=1$$$ then $$$a^b \equiv a^{b\pmod{\varphi(c)}} \pmod{c}$$$. Since MOD is a prime, $$$\varphi(MOD)=MOD - 1$$$. Thus $$$a^{b^c} \equiv a^{b^c \pmod{MOD - 1}}$$$

nitin12384

My solution for Josephus queries.
I actually simulated the selection process iteratively, instead of recursively reducing it to smaller subproblem.

Before every iteration, the current set of numbers is stored with three number : $$$st$$$, $$$end$$$, $$$period$$$.
It implies that the current set contains these numbers $$$[st, st+period, st+2*period, ... end]$$$
Then we just simulate how the numbers will be chosen and find $$$cntchoosen$$$ denoting the number of elements chosen in this iteration.
If $$$k \le cntchoosen $$$, then we will just choose the $$$k$$$ th element of current set, else we continue the iterations.

Here is the accepted code.

Accepted Code

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef pair<int, int> pii;
 
#define endl "\n"
#define pb push_back
#define mod7 1000000007
#define mod9 1000000009
#define all(v) v.begin(),v.end() 
int dm = 0;
void fastio(){ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
void fileio() {
	#ifndef ONLINE_JUDGE
		freopen("input.txt", "r", stdin);
	#endif
}
 
int query(int n, int k){
    assert(k<=n);
 
    int st = 1;
    int end = n;
    int period = 1;
    int first_choosen = 2;
    if(first_choosen > end) first_choosen = st;
    int ans = -1;
    while(k>0){
        assert(st <= first_choosen && first_choosen <= end);
        if(st==end){
            ans = st;
            assert(k == 1);
            break;
        }
 
        assert((first_choosen - st) % period == 0);
 
        int jump_period = period*2;
        bool st_choosen = (first_choosen == st);
        bool end_choosen = (end - first_choosen) % jump_period == 0 ;
        int cnt = (end - st + period ) / period ;
 
        int last_choosen = end;
        if(!end_choosen){
            assert(cnt >= 2);
            last_choosen = end - period;
        }
 
        int cnt_choosen = (last_choosen - first_choosen + jump_period) / jump_period ;
        
        if(k > cnt_choosen){
            k -= cnt_choosen;
 
            if(st_choosen) st = st + period;
            if(end_choosen) end = end - period;
 
            if(end_choosen){
                first_choosen = st + period*2;
                if(first_choosen>end){
                    // too less elements
                    assert(st==end);
                    first_choosen = st;
                }
            }
            else{
                first_choosen = st;
            }
            period = period * 2;
        }
        else{
            ans = first_choosen + jump_period*(k-1);
            break;
        }
    }
    return ans;
}
 
void solve(){
    int q;
    cin>>q;
    while(q--){
        int n,k;
        cin>>n>>k;
        int ans = query(n,k);
        cout << ans << endl;
    }
}
 
int main(){
    #ifndef ONLINE_JUDGE
        dm = 1;
	#endif
    if(!dm)fastio();
    fileio();
    solve();
    return 0 ;
}

I came up with a different solution for Inversion Probability.

Lets denote $$$SS[i]$$$ by number of all unique arrays of size $$$i$$$. We can find using this way. $$$SS[i] = r[1]*r[2] ... r[i]$$$

Lets denote $$$sumf[y][i]$$$ by sum of frequency of $$$y$$$ in all unique arrays of size $$$i$$$. We can find using this way. $$$sumf[y][i] = r[i]*sumf[y][i-1] + (j<=r[i] ? SS[i-1]:0)$$$

Lets denote max value of $$$r[i]$$$ by $$$mx$$$.

Lets denote $$$sum[i]$$$ by the sum of inversion count of all unique arrays of size $$$i$$$. $$$sum[i] = sum[i-1]*r[i-1] + \sum_{x=1}^{x=r[i]} \sum_{y=x+1}^{y=mx} sumf[y][i-1] $$$

Finally our answer is $$$sum[n] / SS[n]$$$

Complexity : $$$O(n*max(r[i])*max(r[i]))$$$ Complexity can be bought down to $$$O(n*max(r[i]))$$$ by computing the prefix sum of frequencies.

Accepted Code :

#include <bits/stdc++.h>
using namespace std;
 
void fastio(){ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
typedef long double ld;
void solve(){
    
    int n;
    cin>>n;
    int mx = 100;
    vector<int> r(n+1);
    for(int i=1; i<=n; i++) cin>>r[i];
    mx = *max_element(r.begin(), r.end());
    vector<ld> SS(n+1);
    vector<vector<ld>> sumf(mx+1, vector<ld>(n+1, 0));
    // sumf[j][i]
    vector<ld> sum(n+1);
 
    SS[1] = r[1];
    for(int i=2; i<=n; i++){
        SS[i] = SS[i-1] * r[i];
    }
 
    for(int j=1; j<=mx; j++){
        if(j > r[1]){
            sumf[j][1] = 0;
        }
        else{
            sumf[j][1] = 1;
        }
        for(int i=2; i<=n; i++){
            sumf[j][i] = sumf[j][i-1] * (r[i]);
            if(j <= r[i]){
                sumf[j][i] += SS[i-1] ;
            }
        }
    }
 
    sum[1] = 0 ;
    for(int i=2; i<=n; i++){
        sum[i] = sum[i-1]*r[i];    
        for(int x=1; x<=r[i]; x++){
            ld cntbig = 0;
            for(int y=x+1; y<=mx; y++){
                cntbig += sumf[y][i-1];
            }
            sum[i] += cntbig;
        }
    }
 
    ld ans = sum[n] / SS[n];
    cout << fixed << setprecision(6) << ans << endl;
 
}
 
int main(){
    fastio();
    solve();
    return 0 ;
}

djay24

22 months ago, # ^ |

nitin sir orz

I do not understand the importance of the problem "Counting Divisors". We previously calculate all answers and then outputting them. I count each prime factor and then apply Combinatorics.

Tle on two test case

ll n;
 cin>>n;
 ll ans=1;
 for(ll i=2;i*i<=n;i++){
  if(n%i==0){
    ll c=0;
    while(n%i==0){
      n=n/i;
      c++;
    }
    ans*=(c+1);
  }
 }
 if(n>1)ans*=2;;
 
 cout<<ans<<endl;

Secondly, I tried to optimize the factor calculation.

Pass

ll n=1000001;
vector<ll> least_prime(n+5);
void leastprime(){
    least_prime[1] = 1;
    for (ll i = 2; i <= n; i++)
    {
        if (least_prime[i] == 0)
        {
            least_prime[i] = i;
            for (ll j = i*i; j <= n; j += i)
                if (least_prime[j] == 0)
                   least_prime[j] = i;
        }
    }
}


void chal() {
 ll m;
 cin>>m;
 ll ans=1;
 map<ll,ll> aa;
 while(m>1){
  // cout<<m<<' '<<least_prime[m]<<endl;
  ll x=least_prime[m];
  aa[x]++;
  m=m/least_prime[m];
 }
 for(auto x:aa){
  // cout<<x.fi<<' '<<x.se<<endl;
  ans*=(x.se+1);
 }
 
 cout<<ans<<endl;
 
  
}

ASHWANTH_K

18 months ago, # |

Counting grids is easily solvable with Burnside lemma.

4cases.
— No rotation.
— Rotate 90*.
— Rotate 180*.
— Rotate 270*.

asdasdqwer

11 months ago, # |

A possible solution for Counting Grids:

We can use the Burnside Lemma to solve this task. There are 4 possible rotations that we need to consider: rotations by 0°, 90°, 180° and 270°. For 0°, there are 2^(n*n) possible grids, because each square can have either black or white as a color, and there are n*n squares in the grid. For the rotations by 90° and 270°, there are 2^(n*n/4) possibilities. If you rotate the grid by 90°, only the upper left quarter of the grid is significant. Similarly, for 180°, the upper half of the grid is significant, so the number of possibilities is 2^(n*n/2). Taking the average of all these values yields the correct result.

Make sure to consider the edge case where n is odd, because an odd grid length means that there is a square in the center of the grid, so the number of significant squares increases by one.

Here is a link to a possible solution

actron

Josephus Queries CSES Jan -6-2024

akhilAgrawal

8 months ago, # |

Thanks bhaii

tanish.ag1295

5 months ago, # |

#include<bits/stdc++.h>
using namespace std;
#define int long long
int mod=1e9+7;
vector<vector<int>> mult(vector<vector<int>>& a,vector<vector<int>>& b){
    int r=a.size();
    int c=b[0].size();
    int comm=b.size();
    vector<vector<int>> ans(r,vector<int>(c,0));
    for(int i=0;i<r;i++){
        for(int j=0;j<c;j++){
            for(int k=0;k<comm;k++){
                ans[i][j] = (ans[i][j] + (a[i][k] * b[k][j])%mod)%mod;
            }
        }
    }
    return ans;
}
int func(int n,vector<vector<int>>& mat,int node){
    vector<vector<int>> ans(n,vector<int>(n,0));
    for(int i=0;i<n;i++) ans[i][i]=1;
    while(n>0){
        if(n%2==1){
            n--;
            ans = mult(ans,mat); 
        }
        else{
            n/=2;
            mat = mult(mat,mat);
        }
    }
    return ans[0][node];
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m,k,a,b;
    cin >> n >> m >> k;
    vector<vector<int>>mat(n,vector<int>(n,0));
    for(int i=0;i<m;i++){
        cin >> a >> b;
        mat[a-1][b-1]++;
    }
    cout << func(k,mat,n-1) << endl;
    return 0;
}

Can someone please see what is the inefficiency here? When I manually run it on custom invocation in codeforces it says "Memory limit exceeded" however I have passed all the matrices by reference. Also, the code given above for graph paths — 1 is getting accepting by using a recursive implementation of binary exponentiation. I have used iterative implementation, still it is not accepted. Kindly have a look

Janak217

Imp

bansalarpan4

what if we use pollard rho algorithm to find the factors of numbers from 1 to n . pollard rho has a time comp of (n)^1/4 will it work???

the_pain

Great section

origamyee

3 months ago, # |

There is a typo error in Bracket Sequences II.

We note that the correct formula is $$$\frac{k + 1}{n + k + 1}C^{2n + k}_{n}$$$ instead of $$$\frac{k + 1}{n + k + 1}C^{2n + k}_{k}$$$ by the references.

FHVirus

Bruteforced Grundy's Game, here's the result:

Spoiler

These are the only $$$x$$$'s with $$$SG(x) = 0$$$ under $$$10 ^ 6$$$:

4 7 10 20 23 26 50 53 270 273 276 282 285 288 316 334 337 340 346 359 362 365 386 389 392 566 630 633 636 639 673 676 682 685 923 926 929 932 1222

Maybe this is enough for a proof of the problem?

BTW largest SG value for $$$x \le 10 ^ 6$$$ is 231.

Surge226

2 months ago, # |

Hello everyone, I am not able to understand the solution for Inversion probability. I am taking example as, $$$a[i]=3$$$ and $$$a[j]=5$$$, so here $$$a[j] > a[i]$$$, where $$$i < j$$$, then the total number of inversions would be $$$21, 31, 32 = 3 = \binom{3}{2}$$$, then what does $$$((a[j] - a[i]) * a[i])$$$ is counting? Am I making mistake somewhere in understanding?

iamalizaidi

3 weeks ago, # |

31: Another game

Intuition -: Here we can see that every time player can take 1 coin from a pile. So we can conclude that if a pile has an odd no of coins then the person who will start first will win. So in the list of piles if we have any one odd coin pile then the first player will win otherwise not.

public static void main(String[] args) throws IOException {
        InputReader sc = new InputReader();
        PrintWriter out = new PrintWriter(System.out);
        
        int t = sc.nextInt();
       
        while (t-- > 0) {
            int n = sc.nextInt();
            
            int cnt = 0;
            for(int i = 0 ; i<n; i++) {
                int tmp = sc.nextInt();
                if(tmp % 2 != 0) {
                    cnt++;
                }
            }

            if(cnt > 0) {
                out.println("first");
            }
            else {
                out.println("second");
            }

        }
        
        out.close();
    }

divyamsingal01's blog