慕名已久的神奇题，感觉某些点找到了捷径就来写篇题解。
很显然答案就是 \(a \times b \mod c\)，由于是一次一次加的并不会溢出。
快速乘即可解决，时间复杂度 \(O(\log c)\)。
初始 \(a=1\)，\(b=0\)，\(c=0\)。
重复执行操作：
b <- a+b
a <- 2*b-a+c;
c <- 2*b-a+c;
设操作 \(i\) 次后得到的 \(a\)，\(b\)，\(c\) 分别为 \(a_i\)，\(b_i\)，\(c_i\)。
经过观察发现 \(a_i=F_{i+1}^2\)，\(b_i=F_i F_{i+1}\)，\(c_i=F_i^2\)。
（其中 \(F_i\) 是斐波那契数列，满足 \(F_0=0\)，\(F_1=1\)，\(F_n=F_{n-2}+F_{n-1}\)。)
不放心，尝试用归纳法证明一下：
\(n=0\) 时，成立。
若 \(n=k\) 时成立，
故 \(n=k+1\) 时成立。
答案就是 \(d=a_n-2b_n+c_n=F_{n+1}^2-2F_nF_{n+1}+F_n^2=(F_{n-1}+F_n)^2-4F_n(F_{n-1}+F_n)+F_n^2=F_{n-1}^2\)。
然后可以矩阵乘法，也可以推通项，不过鉴于这里有十个模数推通项可能比较麻烦……
这里模数比较小，放心用矩阵乘法，时间复杂度 \(O(\log n)\)。
简洁易懂，求：
直接上公式即可：
那么模数……没有模数？！
是的，程序会溢出。
但 unsigned long long 溢出会自动对 \(2^{64}\) 取模，可以拿 python 算。用 c++ 的话大概要先把分母拆开除掉再乘起来，比较麻烦。
时间复杂度 \(O(1)\)。
程序用种子生成了一个 01 矩阵。
count1：对于每一个 \(1\)，求矩阵中除了它的 \(1\) 的个数之和。
假设有 \(cnt\) 个 \(1\)，那答案就是 \(cnt(cnt-1)\)。
count2：对于每一个 \(1\)，求矩阵中某个 \(0\) 离它的最短曼哈顿距离之和。
考虑从左上、右上、左下、右下分别 dp ，\(f_{t,i,j}\) 表示方向 \(t\) 上某个 \(0\) 离 \(i,j\) 的最短曼哈顿距离。
转移时，若 \(data_{i,j}=0\)，则 \(f_{t,i,j}=0\)。
否则：
统计时就取 \(4\) 个数组的最小值就好了。
时间复杂度 \(O(nm)\)。
依然是一个 01 矩阵。
count3：求全 1 子矩形的个数。
实现是 \(O(n^6)\) 的……
先预处理 \(f_{i,j}\) 表示 \((i,j)\) 向上最多能延伸多少个 \(1\)。
考虑枚举每个点作为子矩形的右下端点，那么能取的左上端点的范围就是若干个矩形，用单调栈维护。
时间复杂度 \(O(nm)\)。
设 \(f_0=0\)，\(f_n=(af_{n-1}^2+b) \mod c\)，求 \(f_n\)。
看上去可以求通项，然后秒了？
看一眼数据，发现模数很大……不会溢出吗？
是的，又会溢出。
但这次既溢出又要取模，相当于对两个模数取模，就没办法算了。
正常的办法算不了，只能试试乱搞。想一想，这东西的循环节应该不会很长（听说是 \(O(\sqrt{c})\) 的）。
于是上个判圈算法（Floyd 或者 Brent），就能在 285s 后得到答案……
\(16 \times 16\) 的数独？？？
等下，数独不是只能深搜来解吗，它是怎么超时的？
仔细一看，它把 \(2^{n^2}\) 种方案全部尝试一遍，最后再来检查…………
写发正常点的深搜，成功过了前两个点，但是第三个硬是过不去。
考虑一下我们平常怎么开局的：先单看一个数字，把它的某几个位置确定下来，这样填出来的数字就比较多了。
那其实可以让程序把候选数先处理出来，如果某个格子只有一个候选数，就可以直接确定了。
重复几次，填出来的数就比较多了，这时候再去搜就轻松很多。
//task7
#include<bits/stdc++.h>
using namespace std;
const int N=33;
int bl[N][N];
char s[N][N];
int a[N][N],vish[N][N],visl[N][N],visk[N][N];
int dfs(int x,int y){
if(x==16+1) return 1;
int nx,ny;
if(y==16) nx=x+1,ny=1;
else nx=x,ny=y+1;
if(s[x][y]!=‘?‘) return dfs(nx,ny);
for(int i=‘A‘+16-1;i>=‘A‘;i--){
int t=i-‘A‘;
if(!vish[x][t] && !visl[y][t] && !visk[bl[x][y]][t]){
vish[x][t]=visl[y][t]=visk[bl[x][y]][t]=1;
s[x][y]=i;
if(dfs(nx,ny)) return 1;
vish[x][t]=visl[y][t]=visk[bl[x][y]][t]=0;
}
}
s[x][y]=‘?‘;
return 0;
}
int hx[N][N][N],lft[N][N];
int upd(int x,int y){//让这个数把同行/列/块的候选数除掉
int t=s[x][y]-‘A‘;
for(int i=1;i<=16;i++)
for(int j=1;j<=16;j++){
if(i==x || j==y || bl[i][j]==bl[x][y]){
if(!hx[i][j][t]) hx[i][j][t]=1,lft[i][j]--;
}
}
}
void solve(int score){
memset(vish,0,sizeof(vish));
memset(visl,0,sizeof(visl));
memset(visk,0,sizeof(visk));
memset(hx,0,sizeof(hx));
for(int i=1;i<=16;i++)
for(int j=1;j<=16;j++)
lft[i][j]=16;
for(int i=1;i<=16;i++) scanf("%s",s[i]+1);
for(int i=1;i<=16;i++)
for(int j=1;j<=16;j++)
if(s[i][j]!=‘?‘) upd(i,j);
for(int tt=1;tt<=20;tt++) //重复几次
for(int i=1;i<=16;i++)
for(int j=1;j<=16;j++)
if(s[i][j]==‘?‘ && lft[i][j]==1){//只有一个候选数
for(int t=0;t<16;t++){//找出应该填啥
if(!hx[i][j][t]){
s[i][j]=t+‘A‘;
upd(i,j);
break;
}
}
}
for(int i=1;i<=16;i++)
for(int j=1;j<=16;j++){
int t=s[i][j]-‘A‘;
vish[i][t]=visl[j][t]=visk[bl[i][j]][t]=1;
}
//先处理好桶们
dfs(1,1);
while(score--){
for(int i=1;i<=16;i++)
for(int j=1;j<=16;j++)
printf("%c",s[i][j]);
cout<<endl;
}
}
int main(){
for(int i=1;i<=16;i++)
for(int j=1;j<=16;j++)
bl[i][j]=(i-1)/4*4+(j-1)/4+1;
//块的编号
for(int i=1;i<=4;i++) solve(i);
}
枚举 \(7\) 个值在 \([0,n)\) 之间的变量，求这些变量满足某些大小关系的方案数。
看起来是排列组合？很难搞的样子。
实际上因为只有七个变量，可以大胆猜测答案应该是七次多项式，用拉格朗日插值即可。
时间复杂度 \(O(7)\)，当然前提是题目给出的程序跑得出来才行。
愚人节题目！
程序给出了 MD5 的加密程序与答案的加密结果，这样就可以枚举验证答案是否正确了。
Problem1：第一届 NOI 是哪年？
1984。实在不知道可以枚举年份
Problem2：最常见6位的密码是什么？
123456……
Problem3：一个人名，他的照片在这个文件的开头。他来这次冬令营讲课了，但是他没有来这场考试。
chenlijie。
Problem4：答案是3个可见符号。
好家伙都没法猜了，只能枚举了！
枚举所有可见符号，最后答案是 $_$。
Problem5-10：一句名言，其中 Problem9 是两个单词， Problem10 是一个去掉了 - 的长单词。
好家伙提示都不给了？！
如果你发现 Task2 的代码长度不对劲的话，就能发现它下面有个字典（虽然很长就是了）！
再来枚举，枚举出 Problem5-9 分别是 we / hold / these / truths / to be
Problem10 竟然枚举不出来？？？
出题人大概认为选手的英语和历史不错。
事实上，如果你去做了 Task10 的话，就会在第 7054 行的《独立宣言》里发现这句话！（这也能藏……）
答案是 selfevident。
888k 代码？？？
观察一下，大概就是每个字符串对应一个数，要对某些字符串对应的数求和，同样是对 \(2^{64}\) 取模。
let[0]=1;
for(int i=1;i<=26;i++)
for(int j=0;j<26;j++) let[i]+=let[min(i-1,j)];
对于多个字母组成的字符串，发现它对应的数是所有不包含自身的子串对应的数之和。
考虑每个位置的贡献，设 \(f_{i,j}\) 表示长度为 \(i\) 的字符串的第 \(j\) 个位置被算了多少次。
同样写出代码：
for(int t=2;t<=20;t++)
for(int l=1;l<=t;l++)
for(int r=l;r<=t;r++){
if(l==1 && r==t) continue;
//枚举子串
for(int i=l;i<=r;i++) f[t][i]+=f[r-l+1][i-l+1];
//枚举位置
}
最后就简单了，将给出的四篇文章扔进去逐个单词计算即可。
时间复杂度 \(O(n^4+len)\)。
原文：https://www.cnblogs.com/Appleblue17/p/14618916.html