拉格朗日插值

虽然不难，可以轻松使用小学奥数的想法解决，但是我已经小学毕业了，如何更无脑解决这个问题呢？

发现答案无论怎么样都是个多项式，所以考虑一下小范围暴力，然后拉格朗日插值求出远处的答案。

小范围的暴力很好写，直接 O(n^6) 枚举三角形三个点，再用叉积公式计算面积就好了！

怎么插值呢，毕竟是二维的，你可以一维一维的做，先算出来 ans[1,2,3,...,20][m]，再用这个数组叉出来 ans[n][m]。

时间复杂度居然也是 O(1)。

#include<bits/stdc++.h>
#define int long long
#define mod 1000000007
using namespace std;
int quickpow(int a,int b){
    int ret=1;
    while(b){
        if(b&1) ret=ret*a%mod;
        a=a*a%mod;
        b>>=1;
    }return ret;
}
int inv[114514];
void init(int n=114513){
	for(int i=1;i<=n;i++) inv[i]=quickpow(i,mod-2);
}
int lag(vector<pair<int,int> > vec,int x){
	for(auto u:vec){
		if(u.first==x) return u.second;
	}
    int ret=0;
    for(int i=0;i<vec.size();i++){
        int s=1;
        for(int j=0;j<vec.size();j++){
            if(i==j) continue;
            int d=vec[i].first-vec[j].first;
            if(d>0) s=s*(x-vec[j].first)%mod*inv[d]%mod;
            else s=s*(x-vec[j].first)%mod*inv[-d]%mod,s=mod-s;
        }s%=mod;
        ret+=s*vec[i].second%mod;
    }ret%=mod;
    return ret;
}
int ans[21][21];
int Ans[21]; 
signed main(){
	init();
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=20;i++){
		for(int j=1;j<=20;j++){
			for(int x=1;x<=20;x++){
				for(int y=1;y<=20;y++){
					for(int a=1;a<=20;a++){
						for(int b=1;b<=20;b++){
							int lf=0;
							lf+=a==x;
							lf+=a==i;
							lf+=x==i;
							
							lf+=b==y;
							lf+=b==j;
							lf+=y==j;
							
							if(!lf) continue;
							
							int v1x=i-x,v1y=j-y;
							int v2x=a-x,v2y=b-y;
							int S=abs(v1x*v2y-v1y*v2x);
							if(S==2){
								ans[max({i,x,a})][max({j,y,b})]++;
							}
						}
					}
				}
			}
		}
	}
	for(int i=1;i<=20;i++){
		for(int j=1;j<=20;j++){
			ans[i][j]=ans[i][j]+ans[i-1][j]+ans[i][j-1]-ans[i-1][j-1];
		}
	}
	for(int i=1;i<=20;i++){
		vector<pair<int,int> > vec;
		for(int j=3;j<=10;j++){
			vec.push_back({j,ans[i][j]});
		}
		Ans[i]=lag(vec,m);
	}
	vector<pair<int,int> > vec;
	for(int i=3;i<=10;i++) vec.push_back({i,Ans[i]});
	cout<<lag(vec,n)*quickpow(6,mod-2)%mod;
}