2.5UPD J题数据加强了，过不去了，x，y，a是MOD倍数的情况都需要特判，因为如果指数是MOD-1的倍数 ，快速幂返回1就错了。
亲，所以这里建议修改快速幂。。。当然特判x,y,a也可。
已修改能过更新的J。
https://ac.nowcoder.com/acm/contest/3002
A了7题，感觉J应该赛中应该是可以过的，但没考虑a是MOD倍数，b又是MOD-1倍数的情况。。。
补的题感觉都可做，记录一下思维(水一篇博客)。。。
A.honoka和格点三角形 就分别以1为底和以2为底的统计即可。注意别重复，其实也就是n,m多-1的差别。
C.umi和弓道
将每个点与起始点线段与x轴，y轴交点都处理起来，对x轴和y轴的交点分别sort一下，需要找到n-k个挡起来，扫一遍取这些长度中最小的就行了。
注意别用int，-2e9到2e9就爆了，用double和ll都过了。
感觉挺简单的，我咋就没想到分别处理交点呢。
贴个代码
#include <bits/stdc++.h> #ifndef ONLINE_JUDGE #define debug(x) cout << #x << ": " << x << endl #else #define debug(x) #endif using namespace std; typedef long long ll; const int MAXN=2e5+7; const int INF=0x3f3f3f3f; const int MOD=1e9+7; int main() { vector<double>x,y; int x0,y0; scanf("%d%d",&x0,&y0); int n,k; scanf("%d%d",&n,&k); for(int i=0;i<n;++i) { ll a,b; scanf("%lld%lld",&a,&b); if(a*x0<0) y.push_back(y0-1.0*(b-y0)/(a-x0)*(x0)); if(b*y0<0) x.push_back(x0-1.0*(a-x0)/(b-y0)*(y0)); } sort(y.begin(),y.end()); sort(x.begin(),x.end()); double ans=4e18; for(int i=0;i<x.size();++i) { int q=i+n-k-1; if(q>=x.size()) break; ans=min(ans,x[q]-x[i]); } for(int i=0;i<y.size();++i) { int q=i+n-k-1; if(q>=y.size()) break; ans=min(ans,y[q]-y[i]); } if(ans==4e18) puts("-1"); else printf("%.8f ",ans); return 0; }
F.maki和tree 白色的能dfs到的全部归为一个联通快，标记并记录这个联通快的结点数量。然后对于所有的黑色结点，加上他能到的所有白色结点的sum，这些是黑色结点为一端点，白色结点为另一个端点的，再加上对每个白色结点的ans[]*(sum-ans[]),最后除以2即可，相当于一端点在某一个白色结点上，另一端点在其他分支的白色结点上，每个都算了两次除掉即可。
好像也可以树上dp做，但设计状态不太在行。也差不多思路统计答案，好吧我在看看dp咋做的。
#include <bits/stdc++.h> #ifndef ONLINE_JUDGE #define debug(x) cout << #x << ": " << x << endl #else #define debug(x) #endif using namespace std; typedef long long ll; const int MAXN=2e5+7; const int INF=0x3f3f3f3f; const int MOD=1e9+7; int cnt; int vis[MAXN]; vector<int>e[MAXN]; char s[MAXN]; int ans[MAXN]; int sum; void dfs(int u,int fa) { vis[u]=cnt; sum++; for(int i=0;i<e[u].size();++i) { int v=e[u][i]; if(v==fa) continue; if(s[v]=='W' ) dfs(v,u); } } int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin>>n; cin>>(s+1); for(int i=0,x,y;i<n-1;++i) { cin>>x>>y; e[x].push_back(y); e[y].push_back(x); } for(int i=1;i<=n;++i) { sum=0; if(!vis[i]&&s[i]=='W') { cnt++; dfs(i,-1); ans[cnt]=sum; } } ll res=0; for(int i=1;i<=n;++i) { if(s[i]=='B') { int u=i; sum=0; for(int j=0;j<e[u].size();++j) { int v=e[u][j]; if(s[v]=='W') sum+=ans[vis[v]]; } ll t=0; for(int j=0;j<e[u].size();++j) { int v=e[u][j]; if(s[v]=='W') t+=ans[vis[v]]*(sum-ans[vis[v]]); } res+=sum+t/2; } } cout<<res<<endl; return 0; }
I.nico和niconiconi 简单的递推转移。。话说我为什么还是在想别的题的时候忽然才想到dp做这题，刚开始完全没法下手。
J.u's的影响力 本场最大坑题(对我而言)，结论和式子都没什么毛病，就是答案的指数和斐波那契数列相关。
x，y的指数是fib的相邻两项
a的指数 fn=fn-1+fn-2+1，这个与前面的fib数列不同，再构造一个三维矩阵代码量太大。但观察知，正好是前面两个系数相加-1，因为这个递推公式和fib差很近，直觉告诉我肯定有简单的公式。
但赛后不能证明。。。。。。。
这里对指数需要用到欧拉降幂的，就你在矩阵快速幂的时候对MOD-1取模，算实际答案对MOD取模即可。
然后坑点就是，考虑a是MOD的倍数，b是MOD-1的倍数，这样根据我们的运算就会出来0^0，快速幂里返回的是1，其实应该是0。就出现了错误，差不多Case 89%左右会WA。
所以这里减少运算，如果a是MOD的倍数直接输出0即可。然后就过了。。。
太细节了，这个真的想不太到。艾。。。我可以以后在快速幂特判0的答案。
不过话说我比赛if 没return 0也没else 就等于说n=1和n=2的情况我也会继续下面的，但其实是非法的状态，导致我TLE了。。。。。找不出bug点，太蠢啦
#include <bits/stdc++.h>
#define debug(x) cout << #x << ": " << x << endl
#else
#define debug(x)
#endif
using namespace std;
typedef long long ll;
const int Mod = 1e9+6;
const int MOD = 1e9+7;
const int v=2;
struct matrix
{
ll m[v][v];
}Ans, base;
{
memset(Ans.m, 0, sizeof(Ans.m));
for(int i=0; i<v; i++) Ans.m[i][i] = 1;
// memset(base.m, 0, sizeof(base.m));
base={1,1,1,0};
}
{
matrix res={0};
//memset(res.m, 0, sizeof(res.m));
for(int i=0; i<v; i++)
{
for(int j=0; j<v; j++)
{
for(int k=0; k<v; k++)
{
res.m[i][j] += (a.m[i][k] ) * (b.m[k][j] );
res.m[i][j] %= Mod;
}
}
}
return res;
}
inline void Qmat_pow(ll p)
{
while (p)
{
if(p & 1) Ans = mul(Ans, base);
base = mul(base, base);
p >>= 1;
}
}
{
ll res=1;
x%=MOD;
if(x==0) return 0;
while(n)
{
if(n&1) res=(res*x)%MOD;
x=(x*x)%MOD;
n>>=1;
}
return res;
}
ll quickMUL(ll a,ll b) //快速乘法 a*b
{
a%=MOD;
ll res=0;
while(b)
{
if(b&1) res=(res+a)%MOD;
a=(a+a)%MOD;
b>>=1;
}
return res%MOD;
}
{
ll n,f1,f2,a,b;
scanf("%lld%lld%lld%lld%lld",&n,&f1,&f2,&a,&b);
if(n==1) printf("%lld ",f1%MOD);
else if(n==2) printf("%lld ",f2%MOD);
//else if(a%MOD==0) printf("0 ");
else
{
init();
Qmat_pow(n-3);
ll x2=(Ans.m[0][0]+Ans.m[0][1])%Mod;
ll x1=(Ans.m[1][0]+Ans.m[1][1])%Mod;
ll t=(b%Mod)*((x2+x1-1+Mod)%Mod)%Mod;
ll ans1=quick(f2,x2)*quick(f1,x1)%MOD*quick(a,t)%MOD;
printf("%lld ",ans1);
}
return 0;
}