自动搬运

查看原文

来自洛谷，原作者为

	dtcxzyw **

搬运于2025-08-24 22:02:11，当前版本为作者最后更新于2018-05-28 19:14:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

感受

这道题就是标题党。。。

本以为我要像NOI2016旷野大计算那样写个微型编译器。

解题思路

注意到本题的一个性质：只有一个if

程序的执行流程为

• 执行if跳转到的行之前一次

• 迭代执行if与它跳转到的行之间的块

是不是很像Pollard-Rho啊

对于只执行一次的代码，暴力模拟即可

对于迭代块内的代码，可计算出转移矩阵后，用矩阵快速幂在$O(26^3lgn)$的时间内计算迭代n次后寄存器的答案。

转移矩阵的计算

令$A[i][j]$为执行代码前的i寄存器对执行代码后j寄存器的贡献（系数）

执行代码块后的寄存器值$V'[j]=\sum_{i=a}^zA[i][j]V[i]$

首先将A初始化为单位矩阵I，每次执行add操作时将r2的系数加到r1即可。

计算答案

还有一个性质：寄存器的值是非减的，而且if中所判断的数肯定会不停地增长，否则程序将陷入死循环。

在倍增求转移矩阵的幂时顺便判一下上界，我们就可以开始愉快地二分了。

吐槽

数据太水，不爆long long,没用__int128或double等就过了。

代码

#include <cstdio>
#include <cstring>
long long read(){
	long long res=0;
	int c;
	do c=getchar();
	while(c<'0'||c>'9');
	while('0'<=c&&c<='9'){
		res=res*10+c-'0';
		c=getchar();
	}
	return res;
}
int getAlpha(){
	int c,res;
	do c=getchar();
	while(c<'A'||c>'Z');
	res=c;
	while('A'<=c&&c<='Z')c=getchar();
	return res;
}
typedef long long BigInt;
const BigInt one=1;
void print(BigInt x){
	if(x>=10)print(x/10);
	putchar('0'+x%10);
}
const int size=100005;
struct Add{
	int dst,src;
} A[size];
struct Mat{
	BigInt val[26][26];
	int n,m;
	Mat(){}
	Mat(int n,int m):n(n),m(m){}
	void reset(){
		memset(val,0,sizeof(val));
	}
	const BigInt* operator[](int id) const{
		return val[id];
	}
	BigInt* operator[](int id){
		return val[id];
	}
	Mat operator*(const Mat& rhs) const{
		Mat res(n,rhs.m);
		for(int i=0;i<res.n;++i)
			for(int j=0;j<res.m;++j){
				BigInt sum=0;
				for(int k=0;k<m;++k)
					sum+=val[i][k]*rhs[k][j];
				res[i][j]=sum;
			}
		return res;
	}
};
const int end=64;
Mat pt[end+1];
Mat powm(BigInt k){
	Mat res=pt[0];
	for(int i=0;i<end;++i)
		if((k>>i)&1)res=res*pt[i];
	return res;
}
int main(){
	Mat base(1,26);
	for(int i=0;i<26;++i)base[0][i]=read();
	Mat trans(26,26);
	trans.reset();
	for(int i=0;i<26;++i)trans[i][i]=1;
	bool flag=true;
	int acnt=1,dst,key;
	long long gate;
	while(flag){
		switch(getAlpha()){
			case 'A':{
				++acnt;
				A[acnt].dst=getAlpha()-'A';
				A[acnt].src=getAlpha()-'A';
				break;
			}
			case 'I':{
				key=getAlpha()-'A';
				gate=read();
				int line=read();
				for(int i=2;i<line;++i)
					base[0][A[i].dst]+=base[0][A[i].src];
				for(int i=line;i<=acnt;++i)
					for(int j=0;j<26;++j)
						trans[j][A[i].dst]+=trans[j][A[i].src];
				break;
			}
			case 'P':{
				flag=false;
				dst=getAlpha()-'A';
				break;
			}
		}
	}
	BigInt l=1,r=-1;
	for(int i=0;i<end;++i){
		if(i==0)pt[i]=trans;
		else pt[i]=pt[i-1]*pt[i-1];
		Mat end=base*pt[i];
		if(end[0][key]>=gate){
			r=one<<i;
			break;
		}
	}
	if(r==-1)throw;
	BigInt ans;
	while(l<=r){
		BigInt m=(l+r)>>1;
		Mat res=base*powm(m);
		if(res[0][key]>=gate)r=m-1,ans=res[0][dst];
		else l=m+1;
	}
	print(ans);
	return 0;
}