T1
Problem 1. spread
Input file:spread.inOutput file:spread.outTime limit:1 secondMemory limit:256 MBDarrell 所在的国家有 N 个城市，共有 N 1 条输水管道连接它们，使得任意两个城市都可以通过这些输水管道连接起来。有一种破坏力极强的病毒被发现带入了境内，但不知道在哪个城市，现在已知如果病毒在 u 号城市爆发，则其会随着输水管道向向周围的城市不断扩散，但因为一些原因，扩散的速度有可能不一致。问题是，如果 u 号城市爆发病毒，则一段时间后可能的扩散情况有多少种？你需要对每个城市回答该问题。（答案可能很大，你只需要输出取模 109+ 7 的结果即可）。Input第 1 行，有 1 个整数 N，表示城市数目。接下来 N 1 行，每行 2 个整数：u v，表示城市 u 和 v 之间有输水管道。Output输出 1 行，包含 N 个整数，第 i 个整数表示 i 号城市爆发病毒对应的答案。Samplespread.inspread.out41 22 32 45 8 5 5Note样例中，如果 1 号城市爆发病毒，则可能的扩散情况有：[1],[1;2],[1;2;3],[1;2;4],[1;2;3;4]，共 5 种。如果 2 号城市爆发病毒，则可能的扩散情况有：[2],[2;1],[2;3],[2;4],[2;1;3],[2;3;4],[2;1;4],[2;1;3;4]，共 8种。DP+换根
//By SiriusRen#include#include #include using namespace std;const int N=200500,mod=1000000007;int n,a[N],first[N],next[N],v[N],tot,xx,yy,f[N],g[N];void add(int x,int y){v[tot]=y,next[tot]=first[x],first[x]=tot++;}void dfs(int x,int fa){ f[x]=1;int r=1; for(int i=first[x];~i;i=next[i])if(v[i]!=fa){ dfs(v[i],x);r=(1ll*r*f[v[i]])%mod; }f[x]=(f[x]+r)%mod;}int pow(int x,int y){ int r=1; while(y){ if(y&1)r=1ll*r*x%mod; x=1ll*x*x%mod,y>>=1; }return r;}void dfs2(int x,int fa){ for(int i=first[x];~i;i=next[i])if(v[i]!=fa){ g[v[i]]=((1ll*(g[x]-1+mod)%mod*pow(f[v[i]],mod-2)%mod+1)%mod*((f[v[i]]-1+mod)%mod)+1)%mod; dfs2(v[i],x); }}int main(){ freopen("spread.in","r",stdin); freopen("spread.out","w",stdout); memset(first,-1,sizeof(first)); scanf("%d",&n); for(int i=2;i<=n;i++)scanf("%d%d",&xx,&yy),add(xx,yy),add(yy,xx); dfs(1,0);g[1]=f[1];dfs2(1,0); for(int i=1;i<=n;i++)printf("%d ",(g[i]-1+mod)%mod);}
T2
Problem 2. singInput file:sing.inOutput file:sing.outTime limit:1 secondMemory limit:256 MBDarrell 在学唱歌。Darrell 已经学会了一些发音技巧，比如刚唱完 u 号音符就可以接着唱 v 号音符。因为一些特殊的原因，如果 Darrell 能够连续唱出 u1;u2;u3;:::;un，且 u1= u2，那么保证 u1到 un之间至多有 5 种不同的音符。Darrell 想自己编一首自己唱的歌，为了独特，他希望歌中不出现重复的音符，并且想让歌声中包含的音符尽量多，所以，请你告诉他最多能唱多少个音符。Input第 1 行，包含 2 个整数：N M，分别表示 Darrell 会唱的音符数及已经掌握了的发音技巧数。接下来 M 行，每行 2 个整数：u v，表示 Darrell 在唱完 u 后能够接着唱 v。Output输出 1 个整数，表示答案。Samplesing.insing.out4 51 22 33 43 12 44样例解释：可以连续唱出：3;1;2;4 的音符，所以最多为 4 个音符。sing.insing.out7 71 22 33 44 55 24 65 76样例解释：可以连续唱出 1;2;3;4;5;7 的音符，并且无法不重复地唱出更多的音符，所有所以最多为 6个音符
Tarjan+Topsort+next_permutation
//By SiriusRen#includeusing namespace std;const int N=1000050;vector vec[N];queue q;int n,m,xx,yy,first[N],next[N],v[N],tot,cnt,T,mp[5][5],f[5],d[N][5],ans;int low[N],dfn[N],vis[N],stk[N],p[N],id[N],bl[N][5],sz[N],top,du[N],tmp[N],dis[N];void add(int x,int y){v[tot]=y,next[tot]=first[x],first[x]=tot++;}void tarjan(int x){ dfn[x]=low[x]=++cnt,stk[++top]=x,vis[x]=1; for(int i=first[x];~i;i=next[i]) if(!dfn[v[i]])tarjan(v[i]),low[x]=min(low[x],low[v[i]]); else if(vis[v[i]])low[x]=min(low[x],dfn[v[i]]); if(low[x]==dfn[x]){T++;do vis[xx=stk[top--]]=0,bl[T][sz[T]]=xx,p[xx]=T,id[xx]=sz[T]++;while(xx!=x);}}int main(){ freopen("sing.in","r",stdin); freopen("sing.out","w",stdout); memset(first,-1,sizeof(first)); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++)scanf("%d%d",&xx,&yy),add(xx,yy); for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i); for(int i=1;i<=T;i++){ memset(mp,0,sizeof(mp)); for(int j=0;j
T3
Memory limit:256 MBDarrell 在思考一道计算题。给你一个尺寸为 1 N 的长条，你可以在上面切很多刀，要求竖直地切并且且完后每块的长度都是整数。在这种限制下其实只有 N 1 个位置可以切。对于一种切的方案，假如切完后每块的宽度分别是：w1;w2;w3;:::;wk（∑wi= N），那么该种方案对应的完美值为：k∏i=1w2i那么问题来了，给出 M 个位置不能切（如果用 x 表示一个位置，那么切完该位置后长条变为 1 x 和1 (N x) 两块），那么所有合法切法对应的完美值的和是多少呢？（只需要输出模 109+ 7 的结果）Input第 1 行，有 2 个整数：N M，表示长条的总长度及不能切的位置数第 2 行，有 M 个整数：x1;x2;x3;:::;xM表示不能切的位置。Output输出 1 行，包含 1 个整数，表示满足要求的所有切法对应的完美值和。（对 109+ 7 取模后的结果）Samplecount.incount.out3 1213样例解释：一共有两种切法（用切完后的块的宽度表示）：1;2 和 3，则对应答案为：1 22+ 32= 13count.incount.out5 22 366样例解释：一共有四种切法：1;3;1、1;4、4;1 和 5，则对应答案为：1 32 1+1 42+42 1+52= 66count.incount.out10 91 2 3 4 5 6 7 8 9100因为所有能切的位置都不能切，所以只有一种切法（就是不切）：10，对应答案为：102
构造一发矩阵+矩阵快速幂
//By SiriusRen#include#include #include using namespace std;#define int long longconst int mod=1000000007,N=100050;int n,m,xx,a[N];struct Matrix{ int a[3][3];void init(){memset(a,0,sizeof(a));}void Ch(){a[0][0]=a[1][0]=a[1][2]=2,a[0][1]=a[0][2]=a[1][1]=a[2][0]=a[2][2]=1;}void Ch2(){a[0][0]=a[0][1]=a[0][2]=a[1][1]=a[2][2]=1,a[1][2]=2;}}cng,cng2,jy;Matrix operator*(Matrix a,Matrix b){ Matrix c;c.init(); for(int k=0;k<3;k++) for(int i=0;i<3;i++) for(int j=0;j<3;j++) (c.a[i][j]+=a.a[i][k]*b.a[k][j])%=mod; return c;}Matrix operator^(Matrix a,int b){ Matrix r;r.init();r.a[0][0]=r.a[1][1]=r.a[2][2]=1; while(b){ if(b&1)r=r*a; a=a*a,b>>=1; }return r;}signed main(){ freopen("count.in","r",stdin); freopen("count.out","w",stdout); scanf("%lld%lld",&n,&m); for(int i=1;i<=m;i++)scanf("%lld",&a[i]); jy.a[0][0]=1;cng.Ch(),cng2.Ch2(); for(int i=1;i<=m;i++)jy=(jy*(cng^(a[i]-a[i-1]-1)))*cng2; jy=jy*(cng^(n-a[m])); printf("%lld\n",jy.a[0][2]);}
满满的智障气息.