前面是题解，后面是垃圾话
T1 Efim与奇怪的成绩
贪心的找第一个可以四舍五入的，然后往上进位。
T2 Beautiful IP Addresses
因为回文，所以 \(n\ge 7\) 太长了，不合法，并且只用找一半，爆搜 check 即可。
T3 装饰
结论题？发现两个上界：\(\frac{a+b+c}{3},a+b+c-\max(a,b,c)\)，答案就是两者中较小的一个。
假设 \(a\) 最大，
-
当 \(\frac{a+b+c}{3}\le b+c\)，即 \(a\le 2b+2c\)，假设我们先拿 \(3\) 个都有的，然后我们可以用较多的一个替换这些 \(3\) 个都有的中较少的一个，这样一直平衡，最后可以分成 \(\frac{a+b+c}{3}\) 组。
-
当 \(\frac{a+b+c}{3}>b+c\) ，即 \(a>2b+2c\)，此时全都拿两个 \(a\)，一个 \(b\) 或 \(c\) 就行。
T4 最大子矩阵Largest Submatrix
枚举 \(a,b,c\)，然后就是 玉蟾宫。考虑记一下每个位置最多能往上延伸多少行，然后就相当于在每一行中找面积最大，单调栈板子。
T5 P2051 [AHOI2009] 中国象棋
清新小 DP，观察到每行每列最多填两个，设 \(f_{i,j,k}\) 表示填到了第 \(i\) 行，有 \(j\) 列是空列，有 \(k\) 列是只有一个炮的列。
\[\begin{aligned} \begin{cases} f[i][j][k]=f[i][j][k]+f[i-1][j][k]; 这一行不填\\ f[i][j][k]=f[i][j][k]+f[i-1][j+1][k-1]*(j+1);这一行在空列中填一个，此时会增加一个只有一个炮的列\\ f[i][j][k]=f[i][j][k]+f[i-1][j][k+1]*(k+1);这一行在有一个炮的列中填一个\\ f[i][j][k]=f[i][j][k]+f[i-1][j+2][k-2]*(j+2)*(j+1)/2;这一行在空列中填两个\\ f[i][j][k]=f[i][j][k]+f[i-1][j+1][k]*(j+1)*k;这一行在空列和只有一个炮的列中各填一个\\ f[i][j][k]=f[i][j][k]+f[i-1][j][k+2]*(k+2)*(k+1)/2;这一行在只有一个炮的列中填两个; \end{cases} \end{aligned} \]直接 DP 即可。
T6 [BZOJ2813 奇妙的Fibonacci]
设 \(f_i\) 表示斐波那契数第 \(i\) 项，有定理即 \(\gcd(f_i,f_j)=f_{\gcd(i,j)}\)，如果 \(f_i\mid f_j\Leftrightarrow \gcd(f_i,f_j)=f_i\Leftrightarrow\gcd(i,j)=i\Leftrightarrow i\mid j\)，从而有 \(f_i\mid f_j\Leftrightarrow i\mid j\)，所以就是求 \(1\) 到 \(n\) 中每个数的约数个数和约数平方和。
该定理证明如下：
引理1：\(\gcd(f_n,f_{n+1})=1\)
证明：根据 \(\gcd(a,b)=\gcd(a,b-a)\)，有 \(\gcd(f_n,f_{n+1})=\gcd(f_n,f_{n-1}+f_n)=\gcd(f_n,f_n-1)=\cdots=\gcd(f_1,f_2)=1\)。
引理2：\(f_m=f_{m-n-1}\cdot f_n+f_{m-n}\cdot f_{n+1}\)
证明：设 \(f_n=a,f_{n+1}=b\)，有 \(f_{n+2}=a+b,f_{n+3}=a+2b,f_{n+4}=2a+3b,\cdots f_m=f_{m-n-1}\cdot a+f_{m-n}\cdot b=f_{m-n-1}\cdot f_n+f_{m-n}\cdot f_{n+1}\)。
根据上面两个引理，可以得出 \(\gcd(f_n,f_m)=\gcd(f_n,f_{m-n-1}\cdot f_n+f_{m-n}\cdot f_{n+1})=\gcd(f_n,f_{m-n}\cdot f_{n+1})\)，根据引理2，有 \(\gcd(f_n,f_{m-n}\cdot f_{n+1})=\gcd(f_n,f_{m-n})\)，以此类推，\(\gcd(f_n,f_{m-n})=\gcd(f_n,f_{m-n-n})=\cdots=\gcd(f_1,f_{\gcd(n,m)})=f_{\gcd(n,m)}\)，根据更相减损法得证。
显然约数的个数 \(f(x)\) 满足互质积性，而约数平方和 \(sum(x)\) 也满足互质积性。这个比较显然，不证了。
此时 狄利克雷前缀和 可以解决这个问题，时间复杂度 \(\mathcal{O}(n\log\log n)\)，不讲。
此时线性筛就可以解决这个问题。
设 \(cnt_i\) 表示 \(i\) 的最小质因数的次数，\(f_i\) 表示 \(i\) 的约数个数，\(s_i\) 表示 \(i\) 除去所有最小质因数后的数，\(sum_i\) 表示 \(i\) 的约数平方和。
设 \(x=i\cdot p\)，当 \(p\nmid i\) 时，\(cnt_x=cnt_i+1,s_x=s_i,f_x=f_{s_i}\cdot f_p,sum_x=f_{s_i}\cdot f_p\)
当 \(p\mid i\) 时，\(cnt_x=cnt_i+1,s_x=s_i,f_x=f_{s_i}\cdot (cnt_x+1),sum_x=sum_i\cdot p^2\cdot sum_{s_i}\)
还有一个细节，就是 \(f_2=1\)，可以被任何数整除，所以当询问为奇数时特判加上就好。
#include<bits/stdc++.h>
#define int long long
typedef long long ll;
typedef unsigned long long ull;
inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
const int N=1e7+10,mod=1e9+7;
int f[N],sum[N],s[N],p[N],cnt[N],tot;
bool vis[N];
inline int mo(int x){return x<0?(x%mod+mod)%mod:(x>=mod)?x%mod:x;}
signed main(){
freopen("fibo.in","r",stdin);freopen("fibo.out","w",stdout);
std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
int q=read();
int q1=read(),a=read(),b=read(),c=read();
f[1]=1,sum[1]=1;
for(int i=2;i<=c;++i){
if(!vis[i])p[++tot]=i,sum[i]=mo(i*i+1),f[i]=2,s[i]=1,cnt[i]=1;
for(int j=1;j<=tot&&p[j]*i<=c;++j){
int zc=p[j]*i;
vis[zc]=1;
if(i%p[j]==0){
s[zc]=s[i];
cnt[zc]=cnt[i]+1;
f[zc]=(cnt[zc]+1)*f[s[zc]];
sum[zc]=mo(sum[i]*p[j]%mod*p[j]%mod+sum[s[i]]);
break;
}
cnt[zc]=1;
f[zc]=mo(f[p[j]]*f[i]);
sum[zc]=mo(sum[p[j]]*sum[i]);
s[zc]=i;
}
}
int S=0,ans=0;
for(int i=1;i<=q;++i){
S=(S+f[q1]+(q1&1))%mod;
ans=(ans+sum[q1]+4*(q1&1))%mod;
q1=(q1*a+b)%c+1;
}
std::cout<<(ll)S<<'\n'<<(ll)ans<<'\n';
}
点击查看垃圾话
又到六月份了，都过去一年了。