洛谷11月月赛round.2

P3414 SAC#1 - 组合数

题目背景

本题由世界上最蒟蒻最辣鸡最撒比的SOL提供。

寂月城网站是完美信息教室的官网。地址:http://191.101.11.174/mgzd 。

题目描述

辣鸡蒟蒻SOL是一个傻逼,他居然觉得数很萌!

今天他萌上了组合数。现在他很想知道simga(C(n,i))是多少;其中C是组合数(即C(n,i)表示n个物品无顺序选取i个的方案数),i取从0到n所有偶数。

由于答案可能很大,请输出答案对6662333的余数。

输入输出格式

输入格式:

输入仅包含一个整数n。

输出格式:

输出一个整数,即为答案。

输入输出样例

输入样例#1:
3
输出样例#1:
4

说明

对于20%的数据,n <= 20;

对于50%的数据,n <= 1000;

对于100%的数据,n <= 1 000 000 000 000 000 000 (10^18)


2的n-1次方

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const ll MOD=;
ll n;
ll powMod(ll a,ll b){
ll ans=;
for(;b;b>>=,a=(a*a)%MOD)
if(b&) ans=(ans*a)%MOD;
return ans;
}
int main(){
scanf("%lld",&n);
printf("%lld",powMod(,n-));
}



P3413 SAC#1 - 萌数

题目背景

本题由世界上最蒟蒻最辣鸡最撒比的SOL提供。

寂月城网站是完美信息教室的官网。地址:http://191.101.11.174/mgzd 。

题目描述

辣鸡蒟蒻SOL是一个傻逼,他居然觉得数很萌!

好在在他眼里,并不是所有数都是萌的。只有满足“存在长度至少为2的回文子串”的数是萌的——也就是说,101是萌的,因为101本身就是一个回文数;110是萌的,因为包含回文子串11;但是102不是萌的,1201也不是萌的。

现在SOL想知道从l到r的所有整数中有多少个萌数。

由于答案可能很大,所以只需要输出答案对1000000007(10^9+7)的余数。

输入输出格式

输入格式:

输入包含仅1行,包含两个整数:l、r。

输出格式:

输出仅1行,包含一个整数,即为答案。

输入输出样例

输入样例#1:
1 100
输出样例#1:
10
输入样例#2:
100 1000
输出样例#2:
253

说明

记n为r在10进制下的位数。

对于10%的数据,n <= 3。

对于30%的数据,n <= 6。

对于60%的数据,n <= 9。

对于全部的数据,n <= 1000,l < r。


在出题人标程的帮助下终于A掉了

数位DP

逆向思维,求不含回文的数

f[i][j][k]表示到i位i为j i-1为k的不含回文的数的个数

很简单的递推,我用了个sum[i][j]来优化

天际线的处理要注意,一开始就是因为打错了哪里

ans要用f更新,而不是sum,否则还是有可能产生回文,天际线跟其他的不一样i之前还有数

PS:高精度-1挺坑的

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <map>
using namespace std;
const int N=,INF=1e9+,MOD=1e9+;
typedef long long ll;
char l[N],r[N];
int n;
ll f[N][][],sum[N][N];
void dp(int n){
for(int i=;i<=;i++){
for(int j=;j<=;j++) if(i!=j) f[][i][j]=;
sum[][i]=;
sum[][i]=;
}
for(int i=;i<=n;i++)
for(int j=;j<=;j++){
for(int k=;k<=;k++) if(j!=k){
for(int z=;z<=;z++) if(j!=z&&k!=z) f[i][j][k]=(f[i][j][k]+f[i-][k][z])%MOD;
sum[i][j]=(sum[i][j]+f[i][j][k]);
}
}
}
void dec(char s[],int &n){
s[n]--;int tn=n;
while(s[n]<'') s[n]='',s[--n]--;
if(s[]==''){
tn--;
for(int i=;i<=tn;i++) s[i]=s[i+];
}
n=tn;
}
ll sol(char s[],int n){
ll ans=,a[N];
ll tot=;
if(n==||n==) return ;
for(int i=;i<=n;i++) a[i]=s[n-i+]-'',tot=(tot*+s[i]-'')%MOD;
a[n+]=-;
for(int i=;i<=n-;i++)
for(int j=;j<=;j++) ans=(ans+sum[i][j])%MOD; for(int j=;j<a[n];j++) ans=(ans+sum[n][j])%MOD; int flag=;
for(int i=n-;i>=;i--){
for(int j=;j<a[i];j++) if(j!=a[i+]&&j!=a[i+]) ans=(ans+f[i+][a[i+]][j])%MOD;//!!!not sum[i][j] cause huiwen
if(a[i]==a[i+]||a[i]==a[i+]) {flag=;break;}
}
if(!flag) ans++;
return (tot-ans+MOD)%MOD;
}
int main(){
scanf("%s%s",l+,r+);
int len1=strlen(l+),len2=strlen(r+);
dp(len2);
dec(l,len1);
printf("%lld",(sol(r,len2)-sol(l,len1)+MOD)%MOD);
}
上一篇:Uva11729 Commando War


下一篇:poj1274 The Perfect Stall (二分最大匹配)