OpenJ

OpenJ_POJ - C16H 题意： 已知有1个球在x,y点，并按照M条规则(向上下左右复制u,d,l,r个)进行复制，每次使用一条规则，重复N次，问最终所有球的（x+y）的值的总和,并对1e9取模。

数据范围小可能可以暴力，但是1e18的数据规模使用暴力求解显然不太现实， 考虑公式推导， 推导过程如下：

首先考虑一个周期M内的变化情况 已知当前ans=(x+y)，当前球个数为num=1; 每次复制，球的基础贡献为(u+r+d+l)*ans, 考虑坐标的变化,向上向下y±1，向左向右x±1， 复制的球的额外贡献为(u+r-d-l)*num (有num个球参与了复制) 再加上初始的ans, 得到ans=ans*(u+r+d+l+1)+(u+r-d-l)*num; 实际上num的改变系数也是（u+r+d+l+1） 即num'=num*(u+r+d+l+1) 这里得到了两个系数A=(u+r+d+l+1),B=(u+r-d-l); 按照这个公式递推 ans[i]=ans[i-1]*A[i]+B[i]*num[i-1],num[i]=num[i-1]*A[i] ans[i]=ans[i-1]*A[i]+B[i]*(num[i]/A[i-1])

展开后(这里的n其实是m，不要在意 )

这里就可以考虑维护一个（B[i]/A[i]）的前缀和BA[i],以及一个A[i]的前缀积AA[i] 考虑多个循环的情况，按照递推式易得最终表达式 tim=n/m res=n%m, ans[n]=(ans[1]+BA[m]*(tim)+BA[res])*AA[m]^(tim)*AA[res];

推出表达式后按照表达式利用快速幂和逆元就可以完成求解 需要注意负数取模问题

AC代码

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <map> #include <queue> #include <functional> #include <vector> #include <stack> #include <set> #include <bitset> using namespace std; typedef long long ll; const int maxn=1e5+50; const int inf=0x7fffffff; const int mod=1e9+7; const int HASH=131; ll AA[maxn]={1};//系数A的前缀积AA ll BA[maxn]={0};//系数BA ll A[maxn]={1};//系数A,仅用于求系数BA ll quick_pow(ll a,ll b) { ll base=a%mod; ll ans=1; while(b>0) { if(b&1) ans=ans*base%mod; base=base*base%mod; b>>=1; } return ans; } int main() { ll t; cin>>t; while(t--) { ll n,m,x,y; cin>>n>>m>>x>>y; ll s=(x+y);//初始ans if(s<0)//负数取模 { ll tmp=0; tmp=(-s)/mod; s+=(tmp+1)*mod; } s%=mod; for(int i=1;i<=m;i++) { ll u,d,l,r; cin>>u>>d>>l>>r; AA[i]=(u+d+l+r+1)*AA[i-1]%mod; A[i]=(u+r+d+l+1)%mod; BA[i]=((u+r-l-d)*quick_pow(A[i],mod-2)); if(BA[i]<0)//负数取模 { ll tmp=0; tmp=(-BA[i])/mod; BA[i]+=(tmp+1)*mod; } BA[i]=(BA[i]+BA[i-1]+mod)%mod;//n1 } ll tim=(n/m); ll ans=0; ll res=n%m; ans=(s+(BA[m]*(tim%mod))%mod+BA[res])%mod; ans=ans*quick_pow(AA[m],tim)%mod; ans=ans*AA[res]%mod; cout<<ans%mod<<endl; } return 0; }