C
一开始怎么也想不出来，想着这种题应该用DP或者组合数之类的，所以找了一下规律发现一个递推式过了
1
2
| if(s[i]=='0')dp[i]=(dp[i]*2-1);
else dp[i]=(dp[i-1]*3-1)%md;
|
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5+10;
const int md = 1e9+7;
ll dp[N];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
memset(dp,0,sizeof(dp));
dp[1]=2;
string s;
cin>>s;
int i = 0;
while(s[i]=='0')i++;
i++;
int num=1;
bool ok =false;
if(i>=s.size())
{
printf("%d\n",1);
continue;
}
for(;i<s.size();i++,num++)
{
if(s[i]=='0')dp[num+1]=(dp[num]*2-1)%md;
else dp[num+1]=(dp[num]*3-1)%md;
}
printf("%lld\n",dp[num]);
}
}
|
G
这道题看到这个数字就感觉不是个质数，后来验证后到2802阶乘之后就全为0了，然后就可以n方处理区间大小以及和了，然后直接查询即可
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5+10;
ll pre[N];
ll res[N];
ll sum[N];
ll jc[N];
const int md = 998857459;
struct NODE
{
int pos;
ll val;
}a[N];
int main()
{
int n,m;
jc[0]=1;
for(int i=1;i<=3000;i++)
{
jc[i]=(jc[i-1]*i)%md;
}
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
{
int y;
scanf("%d",&y);
pre[i]=jc[y];
}
int cnt = 0;
for(int i=1;i<=n;i++)
{
if(pre[i]!=0)
{
a[++cnt].val=pre[i];
a[cnt].pos=i;
sum[cnt]=sum[cnt-1]+a[cnt].val;
}
}
for(int i=1;i<=cnt;i++)
{
for(int j=i;j<=cnt;j++)
{
int range = a[j].pos-a[i].pos+1;
res[range]=max(res[range],(sum[j]-sum[i-1]+md)%md);
}
}
for(int i=0;i<m;i++)
{
ll x;
scanf("%lld",&x);
int ans = 999999;
for(int i=1;i<=n;i++)
{
if(res[i]>=x)
{
ans=i;
break;
}
}
if(ans==999999)printf("-1\n");
else printf("%d\n",ans);
}
}
|