出题人题解 | #tokitsukaze and Unlimited Array#

原题解链接：https://ac.nowcoder.com/discuss/150249

题解:通过暴力程序可以找到规律，答案等于$A\ast n\mathrm{！}A*n！$,$AA$为最高项的系数。$1e9!1e9!$可以用分块打表实现。

暴力打表，存下$1e7,2e7,3e\mathrm{7....1}e9-1e7,1e91e7,2e7,3e7....1e9-1e7,1e9$。总共$100100$个数。然后比如要求$(2e7-1)!(2e7-1)!$,那就从表中$2e72e7$开始往下接着算。时间复杂度为$O(1e7)O(1e7)$。

证明:多项式数列求差分可以类比一下多项式求微分。 我们先看一下 多项式函数求微分的过程。

$\mathrm{△}y=f(x+\mathrm{△}x)-f(x)=f(x{)}^{\mathrm{\prime }}\mathrm{△}x+o(\mathrm{△}x)△y=f(x+\; △x)-f(x)=f(x)\text{'}△x+o(△x)$然后$lim\mathrm{△}x->0lim\; △x->0$的时候$o(\mathrm{△}x)\mathrm{/}\mathrm{△}xo(△x)/△x$充分小所以等于$00$,因为$o(\mathrm{△}x)o(△x)$对于$\mathrm{△}x△x$是高阶无穷小。

也就是$\mathrm{△}y=f(x{)}^{\mathrm{\prime }}\mathrm{△}x△y=f(x)\text{'}△x$。

这个也就是微分公式。然后离散条件 下$\mathrm{△}x=1△x=1$。

这时候虽然$\mathrm{△}y=f(x{)}^{\mathrm{\prime }}\mathrm{△}x△y=f(x)\text{'}△x$，因为在$\mathrm{△}y=f(x{)}^{\mathrm{\prime }}\mathrm{△}x+o(\mathrm{△}x)△y=f(x)\text{'}△x+o(△x)$这一步的时候，$\mathrm{△}x△x$不充分小(等于$11$)，$o(\mathrm{△}x)o(△x)$不可忽略。

但是我们也可以把它写成$\mathrm{△}y=f(x{)}^{\mathrm{\prime }}\mathrm{△}x+o(\mathrm{△}x)△y=f(x)\text{'}△x+o(△x)$的形式， 把$\mathrm{△}x=1△x=1$代入得$△y=f(x)'+a。

余项a是一个最高项的幂次小于$f(x{)}^{\mathrm{\prime }}f(x)\text{'}$最高项幕次的多项式。

那么 在利用$\mathrm{△}y=f(x{)}^{\mathrm{\prime }}+a△y=f(x)\text{'}+a$迭代求差分的时候，余项$aa$先比$f(x{)}^{\mathrm{\prime }}f(x)\text{'}$差分成$00$。

也就是不用考虑$aa$对第$nn$阶差分产生的贡献。

则最终产生贡献的式子为$\mathrm{△}y=(x{)}^{\mathrm{\prime }}△y=(x)\text{'}$。

答案的贡献就是$nn$阶多项式的$nn$阶导数，记为f(x)^(n)。

由多项式高阶求导公式得f(x)^(n)=A*n!。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll block = 1e7;
const ll mod = 1e9+7;
map<ll,ll> sheet= {{0,1},{10000000,682498929},{20000000,491101308},{30000000,76479948},{40000000,723816384},{50000000,67347853},{60000000,27368307},{70000000,625544428},{80000000,199888908},{90000000,888050723},{100000000,927880474},{110000000,281863274},{120000000,661224977},{130000000,623534362},{140000000,970055531},{150000000,261384175},{160000000,195888993},{170000000,66404266},{180000000,547665832},{190000000,109838563},{200000000,933245637},{210000000,724691727},{220000000,368925948},{230000000,268838846},{240000000,136026497},{250000000,112390913},{260000000,135498044},{270000000,217544623},{280000000,419363534},{290000000,500780548},{300000000,668123525},{310000000,128487469},{320000000,30977140},{330000000,522049725},{340000000,309058615},{350000000,386027524},{360000000,189239124},{370000000,148528617},{380000000,940567523},{390000000,917084264},{400000000,429277690},{410000000,996164327},{420000000,358655417},{430000000,568392357},{440000000,780072518},{450000000,462639908},{460000000,275105629},{470000000,909210595},{480000000,99199382},{490000000,703397904},{500000000,733333339},{510000000,97830135},{520000000,608823837},{530000000,256141983},{540000000,141827977},{550000000,696628828},{560000000,637939935},{570000000,811575797},{580000000,848924691},{590000000,131772368},{600000000,724464507},{610000000,272814771},{620000000,326159309},{630000000,456152084},{640000000,903466878},{650000000,92255682},{660000000,769795511},{670000000,373745190},{680000000,606241871},{690000000,825871994},{700000000,957939114},{710000000,435887178},{720000000,852304035},{730000000,663307737},{740000000,375297772},{750000000,217598709},{760000000,624148346},{770000000,671734977},{780000000,624500515},{790000000,748510389},{800000000,203191898},{810000000,423951674},{820000000,629786193},{830000000,672850561},{840000000,814362881},{850000000,823845496},{860000000,116667533},{870000000,256473217},{880000000,627655552},{890000000,245795606},{900000000,586445753},{910000000,172114298},{920000000,193781724},{930000000,778983779},{940000000,83868974},{950000000,315103615},{960000000,965785236},{970000000,492741665},{980000000,377329025},{990000000,847549272},{1000000000,698611116}};
int main(){
    ll n,m;
//    scanf("%d%d",&n,&m);
    cin>>n>>m;
    ll top = 0;
    for (int i=0;i<m;i++){
        ll x,y;
        //scanf("%d%d",&y,&x);
        cin>>y>>x;
        if (x == n){
            top = y;
        }
    }
    ll idx = n/block*block;
    assert(sheet.find(idx) != sheet.end());
    ll ans = sheet[idx];
    for (ll i=idx+1;i<=n;i++){
        ans = ans * i % mod;
    }
    ans = ans * top % mod;
    cout<<ans<<endl;
    return 0;
}