Submission #3414116
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];//数字の位置 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); } } answer %= 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 | 2598 Byte |
Status | WA |
Exec Time | 670 ms |
Memory | 24668 KB |
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 600 | ||||||
Status |
|
|
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 | 654 ms | 23900 KB |
mx.txt | AC | 670 ms | 23772 KB |
rnd_0.txt | WA | 545 ms | 23900 KB |
rnd_1.txt | WA | 475 ms | 24668 KB |
rnd_2.txt | WA | 144 ms | 12768 KB |
rnd_3.txt | WA | 126 ms | 10464 KB |
rnd_4.txt | WA | 211 ms | 17888 KB |
sample1.txt | AC | 21 ms | 9172 KB |
sample2.txt | AC | 21 ms | 11220 KB |
sample3.txt | AC | 21 ms | 9172 KB |