Submission #1493976
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, pii> pip;
typedef pair<pll, pll> P;
const ll INF = 1ll<<29;
const ll MOD = 1000000007;
const double EPS = 1e-9;
const bool debug = 0;
//---------------------------------//
ll mod_pow(ll x, ll n, ll mod) {
if (n == 0) return 1;
ll res = mod_pow(x * x % mod, n / 2, mod);
if (n & 1) res = res * x % mod;
return res;
}
ll mulm(ll a, ll b) { return a * b % MOD; }
ll divm(ll a, ll b) { return a * mod_pow(b, MOD - 2, MOD) % MOD; }
ll subm(ll a, ll b) { return (a - b + MOD) % MOD; }
ll addm(ll a, ll b) { return (a + b) % MOD; }
int N, T;
int y[112345];
int main() {
cin >> N;
REP(i, N + 1) scanf("%d", y + i);
cin >> T;
if (N >= T) {
cout << y[T] << endl;
return 0;
}
ll sp = 1;
REP(i, N + 1) sp = mulm(sp, subm(T, i));
ll p = 1;
FOR(i, 1, N + 1) p = mulm(p, subm(0, i));
ll ans = 0;
REP(i, N + 1) {
ll now = mulm(y[i], divm(sp, subm(T, i)));
if (i > 0) {
p = divm(p, (-(N - i + 1) + MOD) % MOD);
p = mulm(p, i);
}
ans = addm(ans, divm(now, p));
}
cout << ans << endl;
return 0;
}
Submission Info
Submission Time
2017-08-07 15:45:14+0900
Task
D - 見たことのない多項式
User
tkmst201
Language
C++14 (GCC 5.4.1)
Score
100
Code Size
1591 Byte
Status
AC
Exec Time
220 ms
Memory
640 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:38:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
REP(i, N + 1) scanf("%d", y + i);
^
Judge Result
Set Name
Sample
Subtask1
Subtask2
Subtask3
Score / Max Score
0 / 0
40 / 40
40 / 40
20 / 20
Status
Set Name
Test Cases
Sample
sample_01.txt, sample_02.txt
Subtask1
sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt
Subtask2
sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt
Subtask3
sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask3_01.txt, subtask3_02.txt, subtask3_03.txt, subtask3_04.txt, subtask3_05.txt, subtask3_06.txt, subtask3_07.txt
Case Name
Status
Exec Time
Memory
sample_01.txt
AC
1 ms
256 KB
sample_02.txt
AC
1 ms
256 KB
subtask1_01.txt
AC
1 ms
256 KB
subtask1_02.txt
AC
1 ms
256 KB
subtask1_03.txt
AC
1 ms
256 KB
subtask1_04.txt
AC
1 ms
256 KB
subtask1_05.txt
AC
1 ms
256 KB
subtask1_06.txt
AC
1 ms
256 KB
subtask1_07.txt
AC
1 ms
256 KB
subtask1_08.txt
AC
1 ms
256 KB
subtask1_09.txt
AC
1 ms
256 KB
subtask2_01.txt
AC
1 ms
256 KB
subtask2_02.txt
AC
3 ms
256 KB
subtask2_03.txt
AC
6 ms
256 KB
subtask2_04.txt
AC
5 ms
256 KB
subtask2_05.txt
AC
7 ms
256 KB
subtask2_06.txt
AC
8 ms
256 KB
subtask2_07.txt
AC
8 ms
256 KB
subtask2_08.txt
AC
8 ms
256 KB
subtask3_01.txt
AC
8 ms
256 KB
subtask3_02.txt
AC
216 ms
640 KB
subtask3_03.txt
AC
57 ms
384 KB
subtask3_04.txt
AC
91 ms
384 KB
subtask3_05.txt
AC
219 ms
640 KB
subtask3_06.txt
AC
215 ms
640 KB
subtask3_07.txt
AC
220 ms
640 KB