题目大意:
给一个串
s
s
s(下标从
1
1
1到
n
n
n),和一个变量
i
t
it
it,初始为
0
0
0.要你执行
x
x
x次操作,求最后的串长度对
1
0
9
+
7
10^9+7
109+7取模的结果.
操作如下:
- 将 i t + 1 it+1 it+1
- 将剪贴板的内容替换为 [ i t , n ] [it,n] [it,n]( n n n是当前的串的长度),并在原串中删除 [ i t , n ] [it,n] [it,n]
- 在串的末尾把剪贴板内容粘贴 s i t s_{it} sit 次
题目思路:
靠。。。写的不能再傻逼了。
靠。。。我做法也太傻逼了。
看下正解:
考虑只会执行 x x x次,所以先把前x长度的串维护起来就好了。
每次操作都会增加一部分长度,因为前 x x x串长度都知道了,第 i i i个位置也就知道了,增加的长度就是:
( n n − i ) ∗ ( s [ i ] ) (nn-i)*(s[i]) (nn−i)∗(s[i])
操…
我的思路:
首先找下规律:
用 l a s t [ k ] last[k] last[k]代表第当前 k k k个数字的对长度贡献, c [ k ] c[k] c[k]代表 k k k已经出现了多少次,这样能推出上述公式的规律。
然后 n × 3 n \times 3 n×3模拟就好了…
Code:
/*** keep hungry and calm CoolGuang! ***/
//#pragma GCC optimize(3)
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define dl(x) printf("%lld\n",x);
#define di(x) printf("%d\n",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e18+7;
const int maxn = 1e6+700;
const int M = 1e6+8;
const int mod= 1e9+7;
const double eps = 1e-9;
const double PI = acos(-1);
template<typename T>inline void read(T &a){char c=getchar();T x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
ll n,m,p;
ll last[15],vis[15];
char s[maxn];
int main(){
int T;scanf("%d",&T);
while(T--){
read(n);
memset(vis,0,sizeof(vis));
memset(last,0,sizeof(last));
scanf("%s",s+1);
int cnt = strlen(s+1);
for(int i=1;i<=cnt;i++) last[s[i]-'0']++;
for(int i=1;i;i++){
if(cnt>=n) break;
int len = cnt-i;
for(int j=2;j<=(s[i]-'0');j++){
for(int x=1;x<=len;x++){
s[cnt+1] = s[cnt+1-len];
++cnt;
if(cnt>=n) break;
}
if(cnt>=n) break;
}
}
s[cnt+1] = '\0';
//printf("%s\n",s+1);
int len = strlen(s+1);
for(int i=1;i<=min(n,len*1ll);i++){
vis[s[i]-'0']++;
ll tmp = s[i]-'0';
for(int k=1;k<=3;k++){
last[k] = ((vis[k]*(1ll-tmp)%mod+mod)%mod + tmp*last[k])%mod;
}
}
ll ans = 0;
for(int k=1;k<=3;k++) ans = (ans + last[k])%mod;
dl(ans);
}
return 0;
}
/***
1
24
133321333
***/