期望：250 100+100+50
实际：210 80+100+30
期望：100 实际：80
最后；两个点T了。可能是求逆元的方法太慢了，也可能是闲的又加了一个快速乘的原因。
#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define mod 1000000007
using namespace std;
int n,m;
long long ans;
int read(){
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
long long qmul(long long x,long long m){
long long ret=;
while(m){
if(m&)
ret=(ret+x)%mod;
x=(x+x)%mod;
m>>=;
}
return ret;
}
long long ksm(long long a,long long n){
long long ret=;
while(n){
if(n&)
ret=qmul(ret,a)%mod;
a=qmul(a,a)%mod;
n>>=;
}
return ret;
}
long long ex_gcd(long long a,long long b,long long &x,long long &y,long long &d){
if(!b){ x=;y=;d=a; }
else{
ex_gcd(b,a%b,y,x,d);
y-=(a/b)*x;
}
}
long long inv(long long t,long long p){
long long d,x,y;
ex_gcd(t,p,x,y,d);
return d==?(x%p+p)%p:-;
}
int main(){
//freopen("lpp.in","r",stdin);
freopen("sum.in","r",stdin);
freopen("sum.out","w",stdout);
n=read();m=read();
for(int i=;i<=n;i++){
if(i==){ ans+=m;ans%=mod; }
else{
long long tmp=(ksm(i,m)-)*inv((i-),mod);
ans=ans+qmul(tmp,i);
ans%=mod;
}
}
cout<<ans;
}
80TLE
后来明确了，就是因为在快速幂里套了一个快速乘，所以T了两个点。
#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define mod 1000000007
using namespace std;
int n,m;
long long ans;
int inv[];
int read(){
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
long long qmul(long long x,long long m){
long long ret=;
while(m){
if(m&)
ret=(ret+x)%mod;
x=(x+x)%mod;
m>>=;
}
return ret;
}
long long fastpow(long long a,long long b){
long long s=;
for(;b;b>>=){
if(b&) s=s*a%mod;
a=a*a%mod;
}
return s;
}
int main(){
//freopen("lpp.in","r",stdin);
freopen("sum.in","r",stdin);
freopen("sum.out","w",stdout);
n=read();m=read();
inv[]=;
for(int i=;i<=;i++)
inv[i]=(mod-mod/i)*1ll*inv[mod%i]%mod;
for(int i=;i<=n;i++){
if(i==){ ans+=m;ans%=mod; }
else{
ans=ans+((fastpow(i,m)-)*i)%mod*inv[i-];
ans%=mod;
}
}
cout<<ans;
}
AC
大佬们推公式的思路都好清奇 瑟瑟发抖ing
期望的分：100 实际得分：100
发现大家都用的求最长路，就我思路清奇写了个DP吗？(*^__^*)
/*
期望的分：100
思路：树形dp
*/
#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAXN 50010
using namespace std;
int n,tot;
int dad[MAXN],sum[MAXN],bns[MAXN],size[MAXN],dp[MAXN];
int to[MAXN*],cap[MAXN*],net[MAXN*],head[MAXN];
int read(){
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
void add(int u,int v,int w){
to[++tot]=v;cap[tot]=w;net[tot]=head[u];head[u]=tot;
}
void dfs(int now){
size[now]=;
for(int i=head[now];i;i=net[i])
if(dad[now]!=to[i]){
dad[to[i]]=now;
dfs(to[i]);
sum[now]+=sum[to[i]]+cap[i];
size[now]+=size[to[i]];
}
}
void pre(int now){
if(size[now]==) dp[now]=;
for(int i=head[now];i;i=net[i])
if(dad[now]!=to[i])
pre(to[i]);
}
void work(int now){
int x;
for(int i=head[now];i;i=net[i])
if(dad[now]!=to[i]){
work(to[i]);
dp[now]=min(dp[to[i]]+cap[i]+(sum[now]-sum[to[i]]-cap[i])*,dp[now]);
}
}
int main(){
//freopen("lpp.in","r",stdin);
freopen("tour.in","r",stdin);
freopen("tour.out","w",stdout);
n=read();
for(int i=;i<n;i++){
int u=read();
int v=read();
int w=read();
add(u,v,w);add(v,u,w);
}
memset(dp,0x7f,sizeof(dp));
dfs();
pre();
work();
cout<<dp[];
}
/*
9
1 2 2
2 4 2
2 3 3
1 5 1
5 6 2
5 7 6
6 8 4
6 9 5
*/
AC
期望：50 实际 ：30
读错题目了QwQ想成了只有4和7是幸运数字。
这样竟然还有30分。。良心的出题人给你 笔芯❤❤❤
/*
期望的分：50
思路：暴力dfs
*/
#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define mod 1000000007
using namespace std;
int n,k;
long long ans;
int a[],num[],vis[];
bool vis1[];
int read(){
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
bool judge(){
memset(vis,,sizeof(vis));
for(int i=;i<=k;i++) vis[num[i]]++;
for(int i=;i<=k;i++)
if(vis[num[i]]>=&&vis1[num[i]]) return false;
return true;
}
void dfs(int now,int tot){
if(tot==k){
if(judge()){
ans++;
ans%=mod;
}
return ;
}
if(now>n) return ;
num[tot+]=a[now];dfs(now+,tot+);
dfs(now+,tot);
}
int main(){
//freopen("lpp.in","r",stdin);
freopen("lucky.in","r",stdin);
freopen("lucky.out","w",stdout);
n=read();k=read();
for(int i=;i<=n;i++){
a[i]=read();
int x=a[i],fl=;
while(x){
if(x%!=&&x%!=) fl=;
x/=;
}
if(fl==) vis1[a[i]]=;
else vis1[a[i]]=;
}
dfs(,);
printf("%I64d",ans);
}
50分暴力
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <vector>
#include <map> using std::min;
using std::max; typedef long long i64;
const i64 modulo = i64(1e9) + ;
const int MaxN = ;
const int MaxM = ; i64 power(i64 base, i64 k) {
i64 res = ;
for ( ; k; k >>= ) {
if (k & ) res = (res * base) % modulo;
base = (base * base) % modulo;
}
return res;
} i64 inv(i64 k) {
return power(k, modulo - );
} std::vector<i64> gen_lucky(i64 upper) {
std::vector<i64> res; res.clear();
std::vector<i64> a; a.clear(); a.push_back();
for (int i = ; i < ; ++i) {
std::vector<i64> b; b.clear();
for (size_t j = ; j < a.size(); ++j) {
b.push_back(a[j] * + );
b.push_back(a[j] * + );
}
if (b[] < upper) {
res.insert(res.end(), b.begin(), b.end());
a = b;
} else {
return res;
}
}
return res;
} std::vector<i64> lucky;
std::map<i64, int> lucky2idx;
int n, m, unlucky, k, a[MaxN], cnt[MaxM];
i64 dp[MaxM][MaxM];
i64 f[MaxN]; i64 bincoef(int a, int b) {
i64 tmp = f[a];
tmp = tmp * inv(f[b]) % modulo;
tmp = tmp * inv(f[a-b]) % modulo;
return tmp;
} int main(void)
{ freopen("lucky.in","r",stdin);
freopen("lucky.out","w",stdout);
lucky = gen_lucky(1e9);
m = lucky.size();
for (int i = ; i < m; ++i) {
lucky2idx[lucky[i]] = i;
} scanf("%d%d", &n, &k);
unlucky = n;
for (int i = ; i < n; ++i) {
scanf("%d", a+i);
std::map<i64, int>::iterator it = lucky2idx.find(a[i]);
if (it != lucky2idx.end()) ++cnt[it->second], --unlucky;
} dp[][] = ;
for (int i = ; i < m; ++i) {
for (int j = ; j <= i; ++j) {
dp[i+][j] = (dp[i+][j] + dp[i][j]) % modulo;
dp[i+][j+] += (dp[i+][j+] + (dp[i][j] * cnt[i] % modulo)) % modulo;
}
} f[] = ;
for (int i = ; i <= n; ++i) {
f[i] = f[i-] * i % modulo;
} i64 ans = ;
int st = max(, k-m);
int ed = min(k, unlucky);
for (int i = st; i <= ed; ++i) {
ans += dp[m][k-i] * bincoef(unlucky, i) % modulo;
ans %= modulo;
} printf("%d\n", (int) ans);
fclose(stdin);
fclose(stdout); return ;
}
std