神 TM 有是结论题, 我讨厌结论题 mmp.
杨氏矩阵了解一下 (建议去维基百科).
反正就是推柿子, 使劲推, 最后写起来有一点小麻烦, 但是在草稿纸 (然鹅我木有啊) 上思路清晰的话还是没问题的.
- #include
- #include
- #include
- #define ll long long
- using namespace std;
- const int maxn=2000000,ha=1e9+7;
- inline int read(){
- int x=0; char ch=getchar();
- for(;!isdigit(ch);ch=getchar());
- for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
- return x;
- }
- inline int add(int x,int y){ x+=y; return x>=ha?x-ha:x;}
- inline void ADD(int &x,int y){ x+=y; if(x>=ha) x-=ha;}
- inline int ksm(int x,int y){
- int an=1;
- for(;y;y>>=1,x=x*(ll)x%ha) if(y&1) an=an*(ll)x%ha;
- return an;
- }
- int jc[maxn+5],qz[maxn+5],hz[maxn+5];
- int A,B,C,D,T,ans,MX,MY;
- inline void init(){
- jc[0]=qz[0]=hz[0]=1;
- for(int i=1;i<=maxn;i++){
- jc[i]=jc[i-1]*(ll)i%ha;
- qz[i]=qz[i-1]*(ll)ksm(i,i)%ha;
- }
- for(int i=1;i<=maxn;i++) hz[i]=hz[i-1]*(ll)jc[i]%ha;
- }
- inline int gethz(int x,int len){
- if(!len) return 1;
- return hz[x+len-1]*(ll)ksm(hz[x-1]*(ll)ksm(jc[x-1],len)%ha,ha-2)%ha;
- }
- inline int Get(int x,int y,int derta){
- if(x>y) swap(x,y);
- if(!x) return 1;
- int now=qz[x+derta]*(ll)ksm(qz[derta]*(ll)ksm(jc[x+derta]*(ll)ksm(jc[derta],ha-2)%ha,derta)%ha,ha-2)%ha;
- now=now*(ll)ksm(jc[y+derta]*(ll)ksm(jc[x+derta],ha-2)%ha,x)%ha*(ll)gethz(y+derta+1,x-1)%ha;
- return now;
- }
- int main(){
- init();
- T=read();
- while(T--){
- A=read(),B=read(),C=read(),D=read();
- A-=B-1,C-=D-1,MX=min(A,C),MY=min(B,D);
- if((A>C&&B<D)||(A<C&&B>D))
- ans=Get(A+C-MX*2,MY,0)*(ll)Get(MX,B+D-MY*2,0)%ha*(ll)Get(MX,MY,A+C+B+D-MX*2-MY*2)%ha;
- else ans=Get(A+C-MX,B+D-MY,0);
- ans=jc[A*(ll)B+C*(ll)D-MX*(ll)MY]*(ll)ksm(ans,ha-2)%ha;
- printf("%d\n",ans);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2637925.html