Submission #3416884
Source Code Expand
#include <iostream> #include <algorithm> #include <string> #include <vector> #include <math.h> #define mod 1000000007 typedef long long ll; using namespace std; #define N 100010 ll inv[N],fac[N],ifac[N]; int main(){ int n; cin>>n; int a[n+1]={}; int p[n+1]={}; for(int i=0;i<=n;i++) p[i]=-1; int first=0,second=0; for(int i=0;i<=n;i++){ cin>>a[i]; if(p[a[i]]>=0){ first=p[a[i]]; second=i; }else{ p[a[i]]=i; } } inv[0]=1;inv[1]=1;fac[1]=1;ifac[1]=1;fac[0]=1;ifac[0]=1; for(int i=2;i<=n+2;i++){ inv[i]=(-mod/i)*inv[mod%i]%mod; fac[i]=fac[i-1]*i%mod; ifac[i]=ifac[i-1]*inv[i]%mod; //cout<<inv[i]<<" "<<fac[i]<<" "<<ifac[i]<<endl; } cout<<n<<endl; ll num=first+n-second; //cout<<num<<endl; for(int i=2;i<=n+1;i++){ ll ans=0,sum=0; if(num>=i-1) ans=fac[num]*ifac[i-1]%mod*ifac[num-i+1]%mod; sum=fac[n+1]*ifac[i]%mod*ifac[n+1-i]%mod; ans=(ans+mod)%mod; sum=(sum+mod)%mod; //cout<<i<<" "<<ans<<" "<<sum<<endl; //if(num==0) cout<<sum<<endl; cout<<(sum-ans+mod)%mod<<endl; } return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - 11 |
User | snow39 |
Language | C++14 (GCC 5.4.1) |
Score | 600 |
Code Size | 1154 Byte |
Status | AC |
Exec Time | 190 ms |
Memory | 4352 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 600 / 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 | AC | 190 ms | 4352 KB |
mx.txt | AC | 189 ms | 4352 KB |
rnd_0.txt | AC | 155 ms | 3584 KB |
rnd_1.txt | AC | 133 ms | 3072 KB |
rnd_2.txt | AC | 38 ms | 1024 KB |
rnd_3.txt | AC | 32 ms | 896 KB |
rnd_4.txt | AC | 57 ms | 1536 KB |
sample1.txt | AC | 1 ms | 256 KB |
sample2.txt | AC | 1 ms | 256 KB |
sample3.txt | AC | 1 ms | 256 KB |