Submission #24003726

---

Source Code Expand

#include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)n;++i)
#define each(a,b) for(auto (a): (b))
#define all(v) (v).begin(),(v).end()
#define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end())
#define fi first
#define se second
#define pb push_back
#define show(x) cout<<#x<<" = "<<(x)<<endl
#define spair(p) cout<<#p<<": "<<p.fi<<" "<<p.se<<endl
#define svec(v) cout<<#v<<":";rep(kbrni,v.size())cout<<" "<<v[kbrni];cout<<endl
#define sset(s) cout<<#s<<":";each(kbrni,s)cout<<" "<<kbrni;cout<<endl
#define smap(m) cout<<#m<<":";each(kbrni,m)cout<<" {"<<kbrni.first<<":"<<kbrni.second<<"}";cout<<endl

using namespace std;

typedef pair<int,int>P;

#define MAX_N 100005
#define MOD 1000000007

unsigned inv[MAX_N], fac[MAX_N], finv[MAX_N];

unsigned int add(unsigned int x, unsigned int y){
    return (x + y >= MOD) ? (x + y - MOD) : (x + y);
}

unsigned int sub(unsigned int x, unsigned int y){
    return (x < y) ? (x + MOD - y) : (x - y);
}

unsigned int mul(unsigned int x, unsigned int y){
    return (unsigned long long)x * y % MOD;
}

void make()
{
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for(int i = 2; i < MAX_N; ++i){
        inv[i] = MOD - mul(inv[MOD % i], (MOD / i));
        fac[i] = mul(fac[i - 1], i);
        finv[i] = mul(finv[i - 1], inv[i]);
    }
}

// solve() を呼び出す前に必ず make() を行っておく！！
// deg + 1 個の f(i) = val[i] (i = 0,..., deg) の情報から関数 f を復元し, f(num) を返す
// すべて MOD を法として考えていることに注意
unsigned int solve(int deg, long long num, vector<int>& val)
{
    if((num %= MOD) < 0) num += MOD;
    if(num <= deg) return val[num];
    unsigned int ue = 1;
    vector<unsigned int> lf(deg + 2), rg(deg + 2);
    lf[0] = rg[deg + 1] = 1;
    for(int i = deg; i >= 0; --i){
        rg[i] = mul(rg[i + 1], num - i);
    }
    unsigned int ans = 0;
    for(int i = 0; i <= deg; ++i){
        unsigned int r = mul(finv[deg-i], finv[i]);
        if((deg - i) % 2) r = MOD - r;
        ans = add(ans, mul(mul(lf[i], rg[i + 1]), mul(r, val[i])));
        lf[i + 1] = mul(lf[i], num - i);
    }
    return ans;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> vec(n+1);
    rep(i,n+1){
        cin >> vec[i];
    }
    ll T;
    cin >> T;
    make();
    cout << solve(n, T, vec) << "\n";
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘unsigned int solve(int, long long int, std::vector<int>&)’:
./Main.cpp:59:18: warning: unused variable ‘ue’ [-Wunused-variable]
   59 |     unsigned int ue = 1;
      |                  ^~

Judge Result