B - Problem B. Harvest of Apples
这题是个好题。一开始我以为有什么公式可以直接套，然后就没多想就去找题解了，结果题解说是莫队，突然觉得很有道理。。
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
const int mod=1e9+7;//***************************************************
//返回d=gcd(a,b)；和对应于等式ax+by=d中的x，y
long long extgcd(long long a,long long b,long long &x,long long &y)
{if(a==0&&b==0)return -1;//无最大公约数if(b==0){x=1;y=0;return a;}long long d=extgcd(b,a%b,y,x);y-=a/b*x;return d;//返回gcd(a,b)
}
//****************求逆元******************************
//ax=1(mod n)
long long mod_reverse(long long a,long long n)
{long long x,y;long long d=extgcd(a,n,x,y);if(d==1)return (x%n+n)%n;return -1;
}long long tab1[maxn],tab2[maxn];
void init()
{tab1[0]=1;for(int i=1;i<maxn;i++)tab1[i]=tab1[i-1]*i%mod;tab2[maxn-1]=mod_reverse(tab1[maxn-1],mod);for(int i=maxn-2;i>=0;i--)tab2[i]=tab2[i+1]*(i+1)%mod;
}long long C(int a,int b)
{if(a<b)return 0;return tab1[a]*tab2[b]%mod*tab2[a-b]%mod;
}
//
const int maxm=1e5+5;
int len;
struct Query
{int L,R,block;int idx;Query(int l,int r,int i):L(l),R(r),idx(i){block=L/len;}Query(){}bool operator<(const Query &b)const{if(block!=b.block)return block<b.block;return R<b.R;}
};
Query q[maxm];
long long ans[maxm];
int main()
{init();len=sqrt(1e5);int T;scanf("%d",&T);int n,m;for(int t=1;t<=T;t++){scanf("%d %d",&n,&m);q[t]=Query(m,n,t);}sort(q+1,q+1+T);int L=1,R=1;long long tmpans=2;long long inv2=mod_reverse(2,mod);for(int i=1;i<=T;i++){Query tmp=q[i];while(R<tmp.R){tmpans=((2LL*tmpans%mod-C(R,L))%mod+mod)%mod;R++;}while(L>tmp.L){tmpans=((tmpans-C(R,L))%mod+mod)%mod;L--;}while(R>tmp.R){R--;tmpans=(tmpans+C(R,L))%mod*inv2%mod;}while(L<tmp.L){L++;tmpans=(tmpans+C(R,L))%mod;}ans[tmp.idx]=tmpans;}for(int t=1;t<=T;t++){printf("%lld\n",ans[t]);}return 0;}E - Problem E. Matrix from Arrays
这题规律到是好找，但写的时候想多了，写的有点复杂，结果比赛的时候没过。。
实际上对于每个点求前缀和，然后和往常一样加加减减就行了。
#include<bits/stdc++.h>
using namespace std;
int M[105][105];
int A[15];
int L;
void init()
{int cursor=0;for(int i=0; i<100; i++)for(int j=0; j<=i; j++){M[j][i-j]=A[cursor];cursor=(cursor+1)%L;}/*for(int i=0; i<20;i++){for(int j=0; j<20; j++){printf("%-3d ",M[i][j]);}cout<<endl;}int res=0;for(int i=5;i<=14;i++)for(int j=3;j<=14;j++)res+=M[i][j];cout<<res<<endl;*/for(int i=0; i<2*L; i++){for(int j=0; j<2*L; j++){if(i==0&&j==0)continue;if(i==0)M[i][j]+=M[i][j-1];else if(j==0)M[i][j]+=M[i-1][j];else M[i][j]=M[i][j]+M[i-1][j]+M[i][j-1]-M[i-1][j-1];}}
}int getsum(int x1,int y1,int x2,int y2)
{if(x1==0&&y1==0)return M[x2][y2];else if(x1==0)return M[x2][y2]-M[x2][y1-1];else if(y1==0)return M[x2][y2]-M[x1-1][y2];return M[x2][y2]-M[x1-1][y2]-M[x2][y1-1]+M[x1-1][y1-1];
}long long f(int x,int y)
{int tmp1=x/(2*L),tmp2=y/(2*L);long long res=1LL*tmp1*tmp2*getsum(0,0,2*L-1,2*L-1);res=res+1LL*tmp1*getsum(0,0,2*L-1,y%(2*L));res=res+1LL*tmp2*getsum(0,0,x%(2*L),2*L-1);res=res+getsum(0,0,x%(2*L),y%(2*L));return res;
}int main()
{int T;scanf("%d",&T);while(T--){scanf("%d",&L);for(int i=0; i<L; i++)scanf("%d",&A[i]);init();int Q;scanf("%d",&Q);int x1,y1,x2,y2;while(Q--){scanf("%d %d %d %d",&x1,&y1,&x2,&y2);long long sum=0;sum=f(x2,y2);if(x1)sum-=f(x1-1,y2);if(y1)sum-=f(x2,y1-1);if(x1&&y1)sum+=f(x1-1,y1-1);printf("%lld\n",sum);}}return 0;
}J - Problem J. Let Sudoku Rotate
这题也是直接看题解了。。我是傻逼再看题解。
由于数独的特性，加个判断当前的旋转是否可行就能减少复杂度，然后直接爆搜就完事了。
#include<bits/stdc++.h>
using namespace std;
char s[20][20];
int ans;
char tmp[20];
void rotate(int x,int y)
{x=4*(x-1)+1;y=4*(y-1)+1;int now=0;for(int i=y;i<=y+3;i++){for(int j=x+3;j>=x;j--)tmp[++now]=s[j][i];}now=0;for(int i=x;i<=x+3;i++)for(int j=y;j<=y+3;j++)s[i][j]=tmp[++now];
}
bool vis[30];
bool ok(int x,int y)
{x=4*x,y=4*y;for(int i=1;i<=x;i++){memset(vis,0,sizeof(vis));for(int j=1;j<=y;j++){char tmp=s[i][j];if(tmp>='0'&&tmp<='9')tmp-='0';else tmp-='A',tmp+=10;if(vis[tmp])return 0;vis[tmp]=1;}}for(int i=1;i<=y;i++){memset(vis,0,sizeof(vis));for(int j=1;j<=x;j++){char tmp=s[j][i];if(tmp>='0'&&tmp<='9')tmp-='0';else tmp-='A',tmp+=10;if(vis[tmp])return 0;vis[tmp]=1;}}return 1;
}void dfs(int x,int y,int res)
{if(x==5){ans=min(ans,res);return;}int nxtx=x,nxty=y+1;if(nxty==5){nxty=1;nxtx++;}for(int i=0;i<4;i++){if(i)rotate(x,y);if(ok(x,y))dfs(nxtx,nxty,res+i);}rotate(x,y);
}int main()
{int T;scanf("%d",&T);while(T--){for(int i=1;i<=16;i++)scanf("%s",s[i]+1);ans=1000;dfs(1,1,0);printf("%d\n",ans);}return 0;
}