Submission #3413906


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+2];//i!(mod p)を先にメモ
static long[] factorialRs = new long[n+2];//i!^-1(mod p), pは素数
static long p = 1000000007;

	static void Main()
	{
    n++;
    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;//逆元も先にメモ
    }
    n--;
    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 = (i+1) - numLength[nums[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+1, i+1, p);//nCk(mod p),pは素数
        if(n-lengthMemo >= i)
        {
          answer -= Comb(n-lengthMemo, 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

Submission Time
Task D - 11
User suikameron
Language C# (Mono 4.6.2.0)
Score 0
Code Size 2563 Byte
Status WA
Exec Time 668 ms
Memory 27868 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 600
Status
AC × 3
AC × 4
WA × 6
Set Name Test Cases
Sample sample1.txt, sample2.txt, sample3.txt
All 1.txt, mx.txt, rnd_0.txt, rnd_1.txt, rnd_2.txt, rnd_3.txt, rnd_4.txt, sample1.txt, sample2.txt, sample3.txt
Case Name Status Exec Time Memory
1.txt WA 668 ms 25948 KB
mx.txt AC 648 ms 27868 KB
rnd_0.txt WA 551 ms 25948 KB
rnd_1.txt WA 476 ms 22620 KB
rnd_2.txt WA 146 ms 12768 KB
rnd_3.txt WA 126 ms 12512 KB
rnd_4.txt WA 211 ms 13792 KB
sample1.txt AC 21 ms 9172 KB
sample2.txt AC 20 ms 9172 KB
sample3.txt AC 21 ms 9172 KB