Div 2 536
题目链接 http://codeforces.com/contest/1106
我还是太菜了. jpg
E
傻逼 DP 直接做
我居然调了 1.5h
我真的是太菜了. jpg
堆 + 扫描线直接维护每个位置的贪心结果
然后要么使用干扰
要么就接受贪心的结果
- #include <cstdio>
- #include <algorithm>
- #include <cmath>
- #include <cstring>
- #include <cstdlib>
- #include <queue>
- #include <iostream>
- #include <bitset>
- using namespace std;
- #define N 100005
- #define M 205
- #define ll long long
- int n,m,K,p[N];ll f[N][M];
- struct node{int s,t,d,w;}a[N];
- bool cmp(const node &a,const node &b){return a.s==b.s?a.t<b.t:a.s<b.s;}
- priority_queue<pair<pair<int ,int> ,int>>q;
- int main()
- {
- scanf("%d%d%d",&n,&m,&K);memset(f,0x3f,sizeof(f));
- for(int i=1;i<=K;i++)scanf("%d%d%d%d",&a[i].s,&a[i].t,&a[i].d,&a[i].w);sort(a+1,a+K+1,cmp);
- for(int i=1,j=1;i<=n;i++)
- {
- while(a[j].s<=i&&j<=K)q.push(make_pair(make_pair(a[j].w,a[j].d),j)),j++;
- while(!q.empty()&&a[q.top().second].t<i)q.pop();
- if(!q.empty())p[i]=q.top().second;
- }
- f[1][0]=0;
- for(int i=1;i<=n;i++)
- for(int j=0;j<=m;j++)
- {
- int x=p[i];
- f[i+1][j+1]=min(f[i][j],f[i+1][j+1]);
- if(x)f[a[x].d+1][j]=min(f[i][j]+a[x].w,f[a[x].d+1][j]);
- else f[i+1][j]=min(f[i][j],f[i+1][j]);
- }
- ll ans=1ll<<60;
- for(int i=0;i<=m;i++)ans=min(ans,f[n+1][i]);
- printf("%lld\n",ans);
- }
- F
这不是一个特征多项式优化常系数线性齐次递推裸题嘛!
然后我就开始写了...
然后我发现我不会求 $K$ 次剩余...
然后我就 GG 了...
所以这个题不用会求 $K$ 次剩余...
那么根据原根的性质, 我们可以发现,$K$ 次剩余可以表达为 $\frac{q}{p} \mod 998244352$ 的形式, 其中 $q$ 表达为 $m = 3^q \mod 998244353$,$p=k$
如果 $K$ 不存在逆元的话, 就没有对应的 $K$ 次剩余...
然后, 就可以通过 BSGS+exgcd 求
所以矩阵乘法就能做的题, 为啥我要用特征多项式啊!!!!!
附上代码:
- #include <cstdio>
- #include <algorithm>
- #include <cmath>
- #include <cstring>
- #include <bitset>
- #include <map>
- using namespace std;
- #define N 205
- #define ll long long
- #define mod 998244353
- #define mmod 998244352
- int a[N],b[N],mo[N],tmp[N],n,k,m,ans;
- int q_pow(int x,int n){int ret=1;for(;n;n>>=1,x=(ll)x*x%mod)if(n&1)ret=(ll)ret*x%mod;return ret;}
- void mul(int *a,int *b,int *ret)
- {
- memset(tmp,0,sizeof(tmp));
- for(int i=0;i<k;i++)
- for(int j=0;j<k;j++)
- tmp[i+j]=(tmp[i+j]+(ll)a[i]*b[j])%mmod;
- for(int i=(k<<1)-2;i>=k;i--)if(tmp[i])for(int j=1;j<=k;j++)
- tmp[i-j]=(tmp[i-j]-(ll)tmp[i]*mo[k-j])%mmod;
- for(int i=0;i<k;i++)ret[i]=tmp[i];
- }
- map<int ,int>mp;
- int ex_gcd(int a,int b,int &x,int &y)
- {
- if(!b)return x=1,y=0,a;int ret=ex_gcd(b,a%b,y,x);
- y=y-a/b*x;return ret;
- }
- int BSGS(int x)
- {
- int s=5000,t=1;
- for(int i=0;i<s;i++)mp[int((ll)t*x%mod)]=i,t=t*3ll%mod;
- for(int i=1,now=1;;i++)
- {
- now=(ll)now*t%mod;
- if(mp.find(now)!=mp.end())return i*s-mp[now];
- }
- }
- int main()
- {
- scanf("%d",&k);
- for(int i=1;i<=k;i++)scanf("%d",&mo[k-i]),mo[k-i]=mmod-mo[k-i];
- scanf("%d%d",&n,&m);b[1]=1;a[0]=1;
- if(k==1)b[0]=mmod-mo[0],b[1]=0;
- for(n--;n;n>>=1){if(n&1)mul(a,b,a);mul(b,b,b);}
- int t=(a[k-1]+mmod)%mmod,x=0,y=0;
- int tt=ex_gcd(t,mmod,x,y),kk=BSGS(m);
- if(kk%tt)return puts("-1"),0;
- x=((ll)x*(kk/tt)%mmod+mmod)%mmod;
- printf("%d\n",q_pow(3,x));
- }
来源: http://www.bubuko.com/infodetail-2944927.html