7.27 充分发挥嘴题技能的牛客6
B-Binary Vector
思路
面向样例合理猜测，猜递推公式是 F(n)=F(n-1)*(2^n-1)/2^n
需要降到 O(n)
代码
代码语言：javascript复制#include<bits/stdc .h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define rep(i,s,e) for(int i=s; i<e; i)
using namespace std;
typedef long long ll;
const int maxn = 2e7 5;
const int mod = 1e9 7;
int z[maxn],m[maxn],p[maxn],w[maxn],a[maxn];
int solve(){
int n; sc(n); return pf("%dn",a[n]);
}
int main(){
p[1]=2; rep(i,2,maxn) p[i]=2ll*p[i-1]%mod;
w[1]=500000004; rep(i,2,maxn) w[i]=1ll*w[1]*w[i-1]%mod;
z[1]=1; rep(i,2,maxn) z[i]=1ll*z[i-1]*(p[i]-1 mod)%mod;
m[1]=500000004; rep(i,2,maxn) m[i]=1ll*m[i-1]*w[i]%mod;
rep(i,1,maxn) a[i]=1ll*z[i]*m[i]%mod;
rep(i,2,maxn) a[i]^=a[i-1];
int _; sc(_); while(_--) solve();
}C-Combination of Physics and Maths
题意
给定一个 n*m 大小的矩阵，任意选择行列组成子矩阵，使子矩阵和和最后一列之和的商最大
思路
最优解一定是分母尽量大，而分子尽量小。所以当选择某行作为最底行时，它以上的所有数字都应被选上，所以对每列做一下前缀和，然后再 n^2 暴力求一下最大值就好
G-Grid Coloring
题意
给定一个 n*n 的矩阵，有 k 种颜色，需要给每条边上色。需要满足：
- 所有颜色出现次数相同
- 没有单色环
- 没有单色边
给出一种合法情况
思路
首先特判，n=1 、k=1 还有颜色不能均匀分配的显然不行。对于剩下的合法涂色数，将各边从 1-2n(n 1) 进行编号（左到右上到下），然后按编号从 1-k 循环涂色即可
备注
代码五分钟，特判一小时
H-Harmony Pairs
题意
给定 N ，Nleq 1e100 。问 1-N 中有多少个 (A, B) 对满足 A 的数位和大于 B 的数位和且 Aleq B 。
思路
数位 dp 。dp[pos][d][la][lb] 中，pos 表示第 pos 位，d 表示 B-A ，la 表示当前是否有 A=B ，lb 表示当前是否有 B=N 。d 开到 2000 且从 1000 开始搜防止出现负数非法访问。直接枚举转移。
代码
代码语言：javascript复制#include<bits/stdc .h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=(s); i<(e); i)
#define dep(i,e,s) for(int i=(e); i>=(s); --i)
using namespace std;
typedef long long ll;
const int mod = 1e9 7;
int a[105]; // 位数 一般题目最大1e18
ll dp[105][2005][2][2];
char s[105];
ll dfs(int pos,int d,int la,int lb){
if(pos==-1) return d>1000;
if(dp[pos][d][la][lb]!=-1) return dp[pos][d][la][lb];
ll ans=0; rep(i,0,la?a[pos] 1:10) rep(j,0,lb?i 1:10)
ans =dfs(pos-1,d j-i,la&&i==a[pos],lb&&j==i),ans%=mod;
return dp[pos][d][la][lb]=ans;
}
ll slove(){
mst(dp,-1);
// 多组数据只用最开始mst一次 因为保证边界就可以了
int pos=0,len=strlen(s);
dep(i,len-1,0) a[pos ]=s[i]-'0';
return dfs(pos-1,1000,1,1);
}
int solve(){
scs(s); return pf("%lldn",slove());
}
int main(){
/* int _; sc(_); while(_--) */ solve();
}
