Kishan_template, C++ (gcc)

Kishan_template

#include<bits/stdc++.h>
using namespace std;
#define ll long long int 
#define pb push_back
#define mod 1000000007
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
#define Find find_by_order
#define Pos order_of_key
#define N 1000000
ll power(ll n,ll p)
{
    if(p==0) return 1;
    ll P=power(n,p/2);
    if(p%2==0) return ((((P%mod)*(P%mod))%mod)*(1%mod))%mod;
    if(p%2==1) return ((((P%mod)*(P%mod))%mod)*(n%mod))%mod;
}
ll prime(ll n)
{
    if(n==1) return 0;
    for(ll i=2;i<=sqrt(n);i++)
    {
        if(n%i==0) return 0;
    }
    return 1;
}
ll fact[N+1];
ll inv[N+1];
ll pre()
{
    fact[0]=1;
    inv[0]=1;
    for(int i=1;i<=N;i++)
    {
        fact[i]=(fact[i-1]*i)%mod;
        inv[i]=power(fact[i],mod-2)%mod;
    }
}
ll ncr(ll n,ll r)
{
    if(n<r) return 0;
    if(r==0 || r==n) return 1;
    return (((fact[n]*inv[r])%mod)*inv[n-r])%mod;
}
#include<bits/stdc++.h>
using namespace std;
#define ll int 
#define pb push_back
#define mod 1000000007
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
#define ordered_set tree<pair<ll,ll>, null_type,less<pair<ll,ll>>, rb_tree_tag,tree_order_statistics_node_update> 
#define Find find_by_order
#define Pos order_of_key
#define N 1000000
#define F(i,n) for(int i=1;i<=n;i++)
#define f(i,n) for(int i=0;i<n;i++)
struct ft {
    vector<ll> bit;
    ll n;
    ft(ll n1) {
        n = n1;
        bit.assign(n,0);
    }
    ll sum(ll r) {
        ll ret = 0;
        for(; r >= 0; r = (r&(r+1))-1)
            ret += bit[r];
        return ret;
    }
    void add(ll idx, ll d) {
        for(; idx < n; idx = idx | (idx+1))
            bit[idx] += d;
    }
    ll sum(ll l, ll r) {
        return sum(r) - sum(l-1);
    }
};
int main()
{
    ll n,k;
    cin>>n>>k;
    
    
    ll a[n+1],mi[n+1],ma[n+1];
    ft s(n+k+5);    
    f(i,n)
    {
        s.add(k+i+1,1);
        mi[i+1]=i+1;
        ma[i+1]=i+1;
        a[i+1]=k+i+1;
    }
    f(i,k)
    {
        ll x;
        cin>>x;
        
        ll x1=s.sum(a[x]);
        s.add(a[x],-1);
        ma[x]=max(ma[x],x1);
        mi[x]=1;
        a[x]=k-i;
        s.add(k-i,1);
    }
    F(i,n)
    {
        ll x1=s.sum(a[i]);
        ma[i]=max(ma[i],x1);
        mi[i]=min(mi[i],x1);
        cout<<mi[i]<<" "<<ma[i]<<"\n";
    }
}
int main()
{
    pre();
    ll n,k;
    cin>>n>>k;
    
    ll ans=0;
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=n;j++)
        {
            ll ans1=((((ncr(n,i)*ncr(n,j))%mod)*(power(k-1,n*(i+j)-i*j))%mod)*power(k,n*n-n*(i+j)+i*j))%mod;
             if((i+j)%2==0) ans=(ans+ans1)%mod;
            else ans=(ans-ans1+mod)%mod;
        }
    }
    cout<<ans;
}


run \| edit \| history \| help	0