Submission #340104

#	Time	Username	Problem	Language	Result	Execution time	Memory
340104		KWang31	Asceticism (JOI18_asceticism)	Java	100 / 100	202 ms	11160 KiB

asceticism

import java.io.*; import java.util.*;
public class asceticism{
  static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        
    } 
    public static class Pair implements Comparable<Pair>{
        int vtx; int val;
        public Pair(int a, int b){
            this.vtx=a; this.val=b;
        }
        public int compareTo(Pair other){
            if(this.val<other.val)return -1;
            if(this.val>other.val)return 1;
            if(this.vtx<other.vtx)return -1;
            return 1;
        }
    }
    static int MOD=1000000007;
    static int[] rk, p,siz;
    //Consider putting stuff in K groups of increasing stuff
    //Nothing good gets counted twice
    //Consider groups that can't be merged
    //USE PIE!
    public static void main(String[] args){
        FastReader br=new FastReader();
        int N=br.nextInt(); int K=br.nextInt();
        long comb=1;
        long ans=0;
        for (int i = 0; i < K; i++) {
            ans+=(1-2*(i&1))*(pow(K-i,N)*comb)%MOD; ans%=MOD;
            comb*=(N+1-i); comb%=MOD;
            comb*=pow(i+1, MOD-2); //Inverse of i+1 mod MOD
            comb%=MOD;
        }
        System.out.println((ans+MOD)%MOD);
    }
    public static long pow(int b, int e){
        if(e==0)return 1; if(e==1)return b;
        long x=pow(b,e/2); return ((x*x)%MOD)*pow(b,e%2)%MOD;
    }
    public static int find(int x, int[] p){
        if(p[x]==x)return x;
        int ans=find(p[x],p); p[x]=ans; return ans;
    }
    
    public static void merge(int a, int b) {
        if(rk[a]<rk[b]) {
            p[a]=b; siz[b]+=siz[a];
        }else if(rk[a]==rk[b]) {
            p[a]=b; rk[b]++;siz[b]+=siz[a];
        }else {
            p[b]=a; siz[a]+=siz[b];
        }
    }
    
}
//Debugging:
//Are you sure your algorithm is correct?
//Bounds: long
//Special cases: n=0,1?
//Make sure you remove your debugging code before you submit!

• Subtask 1: 4 / 4
• Subtask 2: 20 / 20
• Subtask 3: 25 / 25
• Subtask 4: 51 / 51