Submission #3413805

---

Source Code Expand

using System;
using System.Linq;//リストの使用
using System.Collections.Generic;
class Program
{
static long n = long.Parse(Console.ReadLine());//nCkにおけるnの最大値
static long[] factorials = new long[n+1];//i!(mod p)を先にメモ
static long[] factorialRs = new long[n+1];//i!^-1(mod p), pは素数
static long p = 1000000007;

	static void Main()
	{
    factorials[0] = 1;
    factorialRs[n] = DivideModFactorial(n,p);
    for(long i = 1; i <= n; i++)
    {
      factorials[i] = (factorials[i-1]*i)%p;//i!(mod p)
      factorialRs[n-i] = (factorialRs[n+1-i]*(n+1-i))%p;//逆元も先にメモ
    }
    long[] nums = Array.ConvertAll(Console.ReadLine().Split(' '),long.Parse);
    long[] numLength = new long[n+1];
    long lengthMemo = 0;//同じ数間の距離
    long answer = 0;
    for(long i = 0; i < n+1; i++)
    {
      if(numLength[nums[i]-1] == 0) numLength[nums[i]-1] = i+1;
      else
      {
        lengthMemo = numLength[nums[i]-1] - (i+1);
        break;
      }
    }
    for(long i = 0; i < n+1; i++)
    {
      if(i == 0) answer = n;
      else if(i == n) answer = 1;
      else
      {
        answer = Comb(n, i+1, p);//nCk(mod p),pは素数
        answer -= Comb(n-lengthMemo-1, i, p);
      }
      Console.WriteLine(answer);
    }
		
	}

  static long DivideMod(long x, long a, long p)//戻り値はx^a(mod p)
  {
    long num = 2;
    long answer = 1;
    long check = a;
    long memo = x%p;
    
    while(check > 0)
    {
      if(check % num == num / 2)
      {
        check -= num / 2;
        answer *= memo;
        answer %= p;
      }
    memo *= memo;
    memo %= p;
    num *= 2;
    }
    return answer;
  }

  static long DivideModReverse(long x, long p)//戻り値はx^-1(mod p), pは素数
  {
    long answer = DivideMod(x, p-2, p);
    return answer;
  }

  static long DivideModFactorial(long x, long p)//戻り値はx!^-1(mod p), pは素数
  {
    long answer = 1;
    for(long i = x; i >= 2; i--)
    {
      answer *= DivideModReverse(i, p);
      answer %= p;
    }
    return answer;
  }

  static long Comb(long a, long b, long p)//戻り値は組み合わせC(a,b)のmod p
  {
    long answer = 1;
    answer *= factorials[a];
    answer %= p;
    answer *= factorialRs[a-b];//引数a-bは負にならないようにする
    answer %= p;
    answer *= factorialRs[b];
    answer %= p;
    return answer;
  }
  
}

Submission Info

Judge Result