P1050 [NOIP2005 普及组] 循环 day16

 又是一道题做了几个小时

非常痛苦啊！

其实我最开始就理解了题意 可是就是一直没想到要和原数组乘一下才行

非常弱智啊！！！

这道题其实真的非常简单

我们可以按位来获取每一位复原需要的步数

然后乘起来就 错误 了！！！

其实题解十次怎么来的我也不知道

最开始以为用容斥定理可以证明其有一个循环

但是我打表发现并不是这样

12^n 10以内第二位都不是1 而 第15位是1

这样我们就不得不把我们的v1更新成v2 也就是带上之前算的位数

然后来加判断是否

其实类似于迭代加深

但是10是猜的

可是我们要注意的一点就是

无论你需要多少的步数 都是在原来的基础上 加上 乘起来的步数来check

#include <bits/stdc++.h>
using namespace std;
const int N = 18;
const int M = 1e4+10;
const int mod = 1e9+7;
#define int long long
#define endl '\n'
#define Endl '\n'
#define inf 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
int max(int x,int y){return x>y?x:y;}
int min(int x,int y){return x<y?x:y;}
vector<int> mul(vector<int> A, vector<int> B,int r){
    vector<int> C(A.size() + B.size());
    for (int i = 0; i < A.size(); i ++ )
        for (int j = 0; j < B.size(); j ++ )
            C[i + j] += A[i] * B[j];
    for (int i = 0, t = 0; i < C.size() || t; i ++ ){
        t += C[i];
        if (i >= C.size()) C.push_back(t % 10);
        else C[i] = t % 10;
        t /= 10;
    }
    while (C.size() > 1 && !C.back()) C.pop_back();
    while(C.size()>r)C.pop_back();
    return C;
}
signed main() {
    fast
    string s; cin >> s;
    vector<int> v;
    int k; cin >> k;
    int n = s.size();
    for (int i = n - 1; i >= n - k; i--)v.push_back(s[i] - '0');
    vector<int> v1 = v;
    vector<int> v2 = v;
    vector<int> ans;
    ans.push_back(1);
    for (int i = 0; i < k; i++) {
        if(mul(v,v2,k)[i]==v[i])continue;
        int u=1;
        do{
            v2=mul(v1,v2,k),++u;
            if(u>10){cout<<-1<<endl;return 0;}
        }while(mul(v,v2,k)[i]!=v[i]);
        v1=v2;
        vector<int>v3;
        v3.push_back(u);
        ans=mul(ans,v3,1e9);
    }
    for(int i=ans.size()-1;i>=0;i--)cout<<ans[i];
    return 0^0;
}