妈妈啊我今天又智障 了 24 小时！！！！！！！！！！！
= =
这应该是最良心的一场。。。。然而、、、、、我。。。。。
一定是今天和昨天撞了两次头ORZ.....
1、
倒过来做就好了ORZ。。。
我数组开少了一个0...ORZ！！！ 只想呵呵~~
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 #define Maxn 100010 8 #define Maxm 1000010 9 #define Mod 99824435310 #define LL long long11 12 struct node13 {14 LL c,st,k;15 }t[Maxn];16 LL qk[Maxm];17 18 LL val[Maxn],mx[Maxn];19 20 int main()21 {22 LL p,q,l;23 scanf("%lld%lld%lld",&p,&q,&l);24 qk[0]=0;25 for(LL i=1;i<=q;i++)26 {27 scanf("%lld%lld",&t[i].k,&t[i].c);28 t[i].st=qk[0]+1;29 for(LL j=1;j<=t[i].k;j++) scanf("%lld",&qk[++qk[0]]);30 }31 for(LL i=1;i<=p;i++) val[i]=i,mx[i]=l;32 for(LL i=q;i>=1;i--)33 {34 LL nvl=0,nmx=1;35 for(LL j=t[i].st+t[i].k-1;j>=t[i].st;j--)36 {37 nvl=(nvl*mx[qk[j]]+val[qk[j]])%Mod;38 nmx=(nmx*mx[qk[j]])%Mod;39 }40 val[t[i].c]=nvl,mx[t[i].c]=nmx;41 }42 printf("%lld\n",val[1]);43 return 0;44 }
2、
对于这题，真的什么话都不想说。。。
第一眼看过去，重复组合。。。容斥原理。。。
容斥，我还算了算，可能可以过。。。
然后推式子，类似c[sm+n-1][sm]，sm是k减掉一些东西之后剩下的。
于是，在这里，我想了很久，组合数太大了，不会求【<-_<-这人智障！！！！！！
于是我放弃了。。。。
看到题解的我简直哭出来！！！换一换就好了！！！上式=c[sm+n-1][n-1] ，n-1很小啊，直接乘过去，最后/(n-1)!就好了。。
是不是傻，你说你是不是傻！！！！！！！！！！！！！！！！！！
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 #define Mod 998244353 8 #define LL long long 9 #define Maxn 1000001010 11 LL a[30];12 LL n,k;13 LL sum=0,A;14 15 LL qpow(LL x,LL b)16 {17 LL ans=1;18 while(b)19 {20 if(b&1) ans=(ans*x)%Mod;21 x=(x*x)%Mod;22 b>>=1;23 }24 return ans;25 }26 27 28 LL get_c(LL x,LL y)29 {30 LL ans=1;31 for(LL i=1;i<=y;i++) ans=(ans*((x-i+1)%Mod))%Mod;32 return (ans*A)%Mod;33 }34 35 void dfs(LL x,LL sm,LL p)36 {37 if(sm<0) return;38 if(x==n+1)39 {40 if(p==0) sum=(sum+get_c(sm+n-1,n-1))%Mod;41 else sum=(sum+Mod-get_c(sm+n-1,n-1))%Mod;42 return;43 }44 dfs(x+1,sm-a[x]-1,1-p);45 dfs(x+1,sm,p);46 }47 48 int main()49 {50 scanf("%d%d",&n,&k);51 A=1;52 for(int i=1;i<=n-1;i++) A=(A*i)%Mod;53 A=qpow(A,Mod-2);54 for(LL i=1;i<=n;i++) scanf("%d",&a[i]);55 dfs(1,k,0);56 printf("%lld\n",sum);57 return 0;58 }
3、
因为AC了这题就不发牢骚了。。。
刚学会整体二分就直接上了。。。。也是很有勇气。。。。。其实有更快的线段树nlogn方法。
考场整体二分代码：
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 #define Maxn 100010 8 #define LL long long 9 10 int w[Maxn];11 12 struct node13 {14 int l,r,c;15 }t[2*Maxn];16 17 int a1[2*Maxn],a2[2*Maxn],a[2*Maxn];18 int ans[Maxn];19 int n,m;20 21 LL c1[Maxn],c2[Maxn];22 void add(int l,int r,int y)23 {24 for(int i=l;i<=n;i+=i&(-i))25 c1[i]+=y,c2[i]+=l*y;26 r++;27 for(int i=r;i<=n;i+=i&(-i))28 c1[i]-=y,c2[i]-=r*y;29 }30 31 LL query(int l,int r)32 {33 LL ans=0;34 for(int i=r;i>=1;i-=i&(-i))35 ans+=c1[i]*(r+1)-c2[i];36 l--;37 for(int i=l;i>=1;i-=i&(-i))38 ans-=c1[i]*(l+1)-c2[i];39 return ans;40 }41 42 void solve(int x,int y,int l,int r)43 {44 int mid=(l+r)>>1;45 for(int i=l;i<=mid;i++)46 {47 if(t[i].l<=t[i].r) add(t[i].l,t[i].r,t[i].c);48 else add(1,t[i].r,t[i].c),add(t[i].l,n,t[i].c);49 }50 a1[0]=0;a2[0]=0;51 for(int i=x;i<=y;i++)52 {53 int now=query(a[i],a[i]);54 if(now>=w[a[i]]) a1[++a1[0]]=a[i];55 else a2[++a2[0]]=a[i],w[a[i]]-=now;56 }57 for(int i=l;i<=mid;i++)58 {59 if(t[i].l<=t[i].r) add(t[i].l,t[i].r,-t[i].c);60 else add(1,t[i].r,-t[i].c),add(t[i].l,n,-t[i].c);61 }62 for(int i=1;i<=a1[0];i++) a[x+i-1]=a1[i];63 for(int i=1;i<=a2[0];i++) a[x+a1[0]+i-1]=a2[i];64 if(l==r)65 {66 for(int i=1;i<=a1[0];i++) ans[a1[i]]=l;67 for(int i=1;i<=a2[0];i++) ans[a2[i]]=-1;68 }69 else70 {71 int ll=a1[0];72 solve(x,x+ll-1,l,mid);73 solve(x+ll,y,mid+1,r);74 }75 }76 77 int main()78 {79 scanf("%d%d",&n,&m);80 for(int i=1;i<=n;i++) scanf("%d",&w[i]);81 for(int i=1;i<=m;i++)82 {83 scanf("%d%d%d",&t[i].l,&t[i].r,&t[i].c);84 }85 for(int i=1;i<=n;i++) a[i]=i;86 memset(c1,0,sizeof(c1));87 memset(c2,0,sizeof(c2));88 solve(1,n,1,m);89 int ql;90 scanf("%d",&ql);91 for(int i=1;i<=ql;i++)92 {93 int x;94 scanf("%d",&x);95 if(ans[x]==-1) printf("So sad\n");96 else printf("%d\n",ans[x]);97 }98 return 0;99 }
树状数组区间修改区间查询还是很好用啊！！！【你是不是傻，这题明明是区间修改，单点询问。。。
【为什么我的整体二分比别人慢= =
2016-11-14 14:59:34
考noip前这么智障真不是什么好事！！！！