P3216 [HNOI2011]数学作业
题目分析
细心的话你是能够看出以下递推式的（我不够细心）：
其中\(k=\lfloor \log_{10}n\rfloor\)
硬性递推\(O(n^2)\)完全不可过，所以怎样加速递推成了问题。
发现式子仅仅和\(n\)和\(n-1\)相关，可以考虑矩阵快速幂加速递推。
于是乎，我们构造了这样的矩阵：\(\begin{bmatrix}10^k&0&0\\1&1&0\\1&1&1\end{bmatrix}\)，之后写出矩阵乘法和矩阵快速幂即可。
代码实现
点击查看代码
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define ll long long
#define R register
using namespace std;
ll n,m;
inline ll re(){
R ll k=0,f=1ll;
R char ch=getchar();
while(!isdigit(ch)){
if(ch=='-')
f=-1ll;
ch=getchar();
}
while(isdigit(ch)){
k=k*10ll+(ch^48ll);
ch=getchar();
}
return 1ll*k*f;
}
void wr(ll x){
if(x<0){
putchar('-');
x=~x+1;
}
if(x>9)
wr(x/10ll);
putchar(x%10+48ll);
}
struct Matrix{
ll a[3][3];
}A,B,C;
inline void init_(){
A.a[0][0]=1,A.a[0][1]=0,A.a[0][2]=0;
A.a[1][0]=1,A.a[1][1]=1,A.a[1][2]=0;
A.a[2][0]=1,A.a[2][1]=1,A.a[2][2]=1;
for(int i=0;i<3;++i)
B.a[i][i]=1;
}
inline Matrix qtimes(Matrix x,Matrix y){
Matrix z=C;
for(int i=0;i<3;++i)
for(int j=0;j<3;++j)
for(int k=0;k<3;++k)
z.a[i][j]=(z.a[i][j]+x.a[i][k]*y.a[k][j])%m;
return z;
}
inline void qpow(ll a,ll b){
A.a[0][0]=a%m;
Matrix c=C,d=A;
for(int i=0;i<3;++i)
c.a[i][i]=1;
for(;b;b>>=1){
if(b&1)
c=qtimes(c,d);
d=qtimes(d,d);
}
B=qtimes(B,c);
}
signed main(){
n=re(),m=re();
init_();
ll i=10;
while(i<=n){
qpow(i,(i/10)*9);
i*=10;
}
qpow(i,n-(i/10)+1);
wr(B.a[2][0]);
return 0;
}
P3166 [CQOI2014]数三角形
题目分析
既然是要求在格点图上选择三个点组成三角形，那么非法方案是三点共线，所以就可以想到用总方案数减去非法方案数。
总方案数很好计算，只需要计算\(C_{(n+1)\times (m+1)}^3\)就行，问题是在于非法方案数。横向的非法方案数就等于\(C_{m+1}^3\times(n+1)\)，进而纵向的就会等于\(C_{n+1}^3\times (m+1)\)。那么斜着的呢？
假设一个点\((0,0)\)，其右上角有一个点\((x,y)\)与之组成了矩阵，然后将其对角线连接起来，容易发现所能经过的格点数就等于\(\gcd(x,y)+1\)，如下图：
所以我们可以去枚举两个点\((0,n-i)\)和\((j,n)\)，在不包含两个端点的情况下，所经过的点个数就等于\(\gcd(i,j)-1\)，考虑到这样的点分别有\((n-i+1)\)和\((m-j+1)\)个，所以斜线所经过的点的总个数就等于\(\sum_{i=1}^n\sum_{j=1}^m(\gcd(i,j)-1)(n-i+1)(m-j+1)\)，所以最终答案就等于：
\[ans=C_{(n+1)\times (m+1)}^3-C_{m+1}^3\times(n+1)-C_{n+1}^3\times (m+1)-\sum_{i=1}^n\sum_{j=1}^m(\gcd(i,j)-1)(n-i+1)(m-j+1) \]代码实现
点击查看代码
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define ll long long
#define R register
using namespace std;
int n,m;
unsigned ll ans;
inline ll re(){
R ll k=0,f=1ll;
R char ch=getchar();
while(!isdigit(ch)){
if(ch=='-')
f=-1ll;
ch=getchar();
}
while(isdigit(ch)){
k=k*10ll+(ch^48ll);
ch=getchar();
}
return 1ll*k*f;
}
void wr(ll x){
if(x<0){
putchar('-');
x=~x+1;
}
if(x>9)
wr(x/10ll);
putchar(x%10+48ll);
}
inline ll C(ll a,ll b){
ll sum=1;
for(int i=a-b+1;i<=a;++i) sum*=i;
for(int i=2;i<=b;++i) sum/=i;
return sum;
}
inline void myswap(int &a,int &b){
int c=a;
a=b;
b=c;
}
int gcd(int a,int b){
return b?gcd(b,a%b):a;
}
signed main(){
n=re(),m=re();
if(n>m) myswap(m,n);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
ans+=2ll*(n-i+1)*(m-j+1)*(gcd(i,j)-1);
ans=C((n+1)*(m+1),3)-C((n+1),3)*(m+1)-C((m+1),3)*(n+1)-ans;
wr(ans);
return 0;
}
（紫题？你不配
(T2、T3 To be Continued~~