題目
【NOIP提高組模拟1】小L的數列
(File IO): input:seq.in output:seq.out
Time Limits: 1500 ms
Memory Limits: 524288 KB
Description
Input
一行兩個整數n和k。
之後1行k個正整數b1…bk。
之後1行k個正整數f1…fk。
Output
輸出一個整數表示fn
Sample Input
【樣例輸入1】
5 4
1 2 3 4
4 3 2 1
【樣例輸入2】
100000 4
1 2 3 4
12 23 34 45
Sample Output
【樣例輸出1】
27648
【樣例輸出2】
33508797
Data Constraint
對于30%的資料，n≤10000.
對于另外20%的資料，bi=1,n≤1000000.
對于另外20%的資料，f[1]…f[k-1]=1.
對于另外20%的資料，k≤30.
對于100%的資料，1≤k≤200,1≤n≤40000000,1≤bi,fi≤998244352.
Hint
樣例解釋：122333444*4=27648
【NOIP提高組模拟1】夢境
(File IO): input:dream.in output:dream.out
Time Limits: 1000 ms
Memory Limits: 262144 KB
Description
Input
Output
Sample Input
2 2
1 3
2 4
1
3
Sample Output
2
Data Constraint
Hint
【noip提高組模拟1】樹
(File IO): input:tree.in output:tree.out
Time Limits: 1000 ms
Memory Limits: 524288 KB
Description
有一棵n個節點的無根樹，給出其中的m對點對<x,y>。問有多少條樹上的簡單路徑<u,v>滿足該路徑上不存在任何一對給出的點對<x,y>。
這裡我們認為路徑<u,v>和<v,u>是相同的。并且對于題目中給出的點對<x,y>滿足x!=y，對于你要計數的路徑<u,v>滿足u!=v（即單點不算答案）。
Input
第一行兩個正整數n,m。
接下來n-1行每行兩個正整數u,v描述樹上的一條邊。
接下來m行每行兩個正整數x,y描述一對給出的點對。
（注意，這裡我們不保證同樣的點對<x,y>不會重複出現）
Output
一行一個整數，表示滿足要求的樹上簡單路徑的條數。
Sample Input
8 3
1 2
1 3
4 8
2 4
2 5
3 6
3 7
2 3
4 8
6 7
Sample Output
11
Data Constraint
Hint
滿足條件的路徑為<1,2>，<1,3>，<1,4>，<1,5>，<1,6>，<1,7>，<2,4>，<2,5>，❤️,6>，❤️,7>，<4,5>。
總結
今天我的發揮不好啊……
看到T1時，我的感受是：哇塞！又是一波推式子，好像挺難的耶！
然後我就暴力直接推 f k + 1 , f k + 2 ⋯ f n f_{k+1},f_{k+2}\cdots f_n fk+1,fk+2⋯fn，結果推了不到3個數就發現自己推錯了！
于是重推，結果又錯了……3次後，我放棄（部分分70啊，這不是很好水的嗎？）
再看T2，哇塞，好像二分圖最大比對耶！再一看，匈牙利算法的 O ( n m ) O(nm) O(nm)可能過不了100分，但是沒關系！我們有讀入優化，我們有O(2)卡常，我們有光速優化，我們有O(fast)犯罪，我們有底層優化和循環展開，我們還有n^2過100000的信心和決心！ 部分分有70啊！
看看T3，正解玄學，不會。但是分類讨論可以90啊！接近AC啊！
然後我發現T1好像水不到70耶……
不過沒關系，水分加起來一共 50 + 70 + 90 = 210 50+70+90=210 50+70+90=210，拿到這個分數就夠了！
水分大作戰的号角吹響了……
11:20
我＊！T3怎麼碼了一個小時都沒有碼完？我之前真是想得太簡單了！
哎呀，鍊和菊花圖的情況已經打完了，剩下就不打暴力了，直接打表輸出11吧！
趕快自己出個資料……
我＊！怎麼沒輸出？
哦！原來是我忘記打printf了。
诶？怎麼輸出錯了？
哦，打錯了一個字母！
再運作，天哪，怎麼RE了？OMG，11:26了，我要加快速度了！
………………………………
然後就0分了。
咦，T2怎麼WA50了？
總結：時間要規劃好，不要好高骛遠，打題之前要大略地估算一下碼量和實作難度。分情況水分的一定要先調完一個再打另外一個，避免狂碼1.5小時+後爆〇。
題解
T1
直接推 f 是很難的，于是可以考慮推b。
有一個顯然的定理： a b × a c = a b + c , ( a b ) c = a b c a^b\times a^c=a^{b+c},(a^b)^c=a^{bc} ab×ac=ab+c,(ab)c=abc，于是可以處理 f i f_i fi由 f 1 , f 2 ⋯ f k f_1,f_2\cdots f_k f1,f2⋯fk分别乘多少得到。
然後就可以矩陣乘法了。
T2
其實這題是最簡單的，甚至不用二分圖最大比對，一個貪心即可AC。
可以把轉折點從小到大排序，夢境區間按左端點從小到大的順序排序，然後處理轉折點。
如果一個夢境區間的左端點小于等于目前轉折點，那麼我們把它放入一個按右端點從小到大排序的堆裡面。
接下來每次取出堆頂判斷一下就可以了。
T3
先把每一個點求dfs序，這樣相同子樹的點的編号是連續的，處理就友善得多了。
接下來對于每一個詢問(u,v)分類讨論：
- 如果u和v在同一條鍊内，假定u為祖先，那麼u的其他子樹和子樹u以外的所有點都不能與v形成點對；
- 否則，u子樹和v子樹内的所有點都不能形成點對。
那麼，現在問題就轉變為如何處理這些不能形成點對的情況了。
可以用矩形來表示這些情況，如果dfn序為 [ x 1 , x 2 ] [x1,x2] [x1,x2]和 [ y 1 , y 2 ] [y1,y2] [y1,y2]的點不能形成點對，那麼就建一個橫坐标為 [ x 1 , x 2 ] [x1,x2] [x1,x2]，縱坐标為 [ y 1 , y 2 ] [y1,y2] [y1,y2]的矩形。用掃描線處理出矩形總面積，用 n ( n − 1 ) 2 \frac{n(n-1)}{2} 2n(n−1)減去即是答案。
CODE
T1
#include<cstdio>
#include<cstring>
using namespace std;
#define ll long long
#define P 998244352
#define mod 998244353
#define N 205
ll f[N],a[N][N],ans=1,K;
struct matrix
{
ll a[N][N];
matrix(){memset(a,0,sizeof(a));}
inline matrix operator *(const matrix x)
{
matrix res;
for(int i=1;i<=K;i++)
for(int j=1;j<=K;j++)
for(int k=1;k<=K;k++)
res.a[i][j]=(res.a[i][j]+a[i][k]*x.a[k][j])%P;
return res;
}
}A;
inline matrix mulpow(matrix x,int y)
{
matrix s;int i;
for(i=1;i<=K;i++) s.a[i][i]=1;
while(y)
{
if(y&1) s=s*x;
x=x*x,y>>=1;
}
return s;
}
inline ll numpow(ll x,ll y)
{
ll s=1;
while(y)
{
if(y&1) s=s*x%mod;
x=x*x%mod,y>>=1;
}
return s;
}
int main()
{
freopen("seq.in","r",stdin);
freopen("seq.out","w",stdout);
int n,i,j;
scanf("%d%lld",&n,&K);
for(i=1;i<=K;i++) scanf("%lld",&A.a[K+1-i][K]);
for(i=1;i<=K;i++) scanf("%lld",f+i);
if(n<=K){printf("%lld\n",f[n]);return 0;}
for(i=2;i<=K;i++) A.a[i][i-1]=1;
A=mulpow(A,n-K);
for(i=1;i<=K;i++) ans=ans*numpow(f[i],A.a[i][K])%mod;
printf("%lld\n",ans);
return 0;
}
T2
#pragma GCC optimize("Ofast")
#pragma GCC target("sse3","sse2","sse")
#pragma GCC optimize("fast-math","unroll-loops","no-stack-protector")
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
#pragma GCC diagnostic error "-std=c++14"
#include<queue>
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 200005
struct interval
{
int l,r;
bool operator <(const interval y)const
{return r>y.r;}
}a[N],temp;
priority_queue<interval>que;
int b[N],n,m;
char ch;bool use[N];
inline char gc()
{
static char buf[N],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,N,stdin),p1==p2)?EOF:*p1++;
}
inline void read(int &x)
{
while(ch=gc(),ch<'0'||ch>'9');x=ch-'0';
while(ch=gc(),ch>='0'&&ch<='9') x=x*10+ch-'0';
}
bool cmp(interval x,interval y)
{return x.l<y.l||x.l==y.l&&x.r<y.r;}
int main()
{
freopen("dream.in","r",stdin);
freopen("dream.out","w",stdout);
int i,j,ans=0;
read(n),read(m);
for(i=1;i<=n;i++) read(a[i].l),read(a[i].r);
sort(a+1,a+n+1,cmp);
for(i=1;i<=m;i++) read(b[i]);
sort(b+1,b+m+1);
for(i=j=1;i<=m;i++)
{
while(j<=n&&a[j].l<=b[i]) que.push(a[j++]);
if(que.empty()) continue;
else temp=que.top(),que.pop();
while((!que.empty())&&temp.r<b[i]) temp=que.top(),que.pop();
if(temp.r>=b[i]) ans++;
}
printf("%d\n",ans);
return 0;
}
T3
#pragma GCC optimize("Ofast")
#pragma GCC target("sse3","sse2","sse")
#pragma GCC optimize("fast-math","unroll-loops","no-stack-protector")
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
#pragma GCC diagnostic error "-std=c++14"
#include<cstdio>
#include<algorithm>
using namespace std;
#define swap(x,y) x^=y,y^=x,x^=y
#define lson k<<1
#define rson k<<1|1
#define N 100005
struct line{int x,yl,yr,num;}a[N<<2];
struct SegmentTree
{
int num[N*17],sum[N*17];
inline void update(int k,int l,int r)
{
if(num[k]) sum[k]=r-l+1;
else if(l==r) sum[k]=0;
else sum[k]=sum[lson]+sum[rson];
}
inline void add(int k,int l,int r,int x,int y,int z)
{
if(x==l&&r==y) num[k]+=z;
else
{
int mid=l+r>>1;
if(y<=mid) add(lson,l,mid,x,y,z);
else if(x>mid) add(rson,mid+1,r,x,y,z);
else add(lson,l,mid,x,mid,z),add(rson,mid+1,r,mid+1,y,z);
}
update(k,l,r);
}
}tree;char ch;
struct EDGE{int end,nex;}edge[N<<1];
inline char gc()
{
static char buf[N],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,N,stdin),p1==p2)?EOF:*p1++;
}
inline void read(int &x)
{
while(ch=gc(),ch<'0'||ch>'9');x=ch-'0';
while(ch=gc(),ch>='0'&&ch<='9') x=x*10+ch-'0';
}
int fir[N],dfn[N],las[N],f[N][17],s,cnt;
inline bool cmp(line x,line y){return x.x<y.x;}
inline void inc(int x,int y)
{
edge[++s]=(EDGE){y,fir[x]},fir[x]=s;
edge[++s]=(EDGE){x,fir[y]},fir[y]=s;
}
inline void add(int xl,int xr,int yl,int yr)
{
a[++s]=(line){xl,yl,yr,1};
a[++s]=(line){xr+1,yl,yr,-1};
}
void dfs(int k,int from)
{
dfn[k]=++cnt;
for(int i=fir[k];i;i=edge[i].nex)
if(edge[i].end!=f[k][0])
f[edge[i].end][0]=k,
dfs(edge[i].end,k);
las[k]=cnt;
}
inline int getson(int u,int v)
{
for(int i=16;i>=0;i--)
if(dfn[f[v][i]]>dfn[u])
v=f[v][i];
return v;
}
int main()
{
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
int n,m,i,j,u,v,son;
long long ans=0;
read(n),read(m);
for(i=1;i<n;i++)
read(u),read(v),inc(u,v);
dfs(1,0);
for(j=1;j<17;j++)
for(i=1;i<=n;i++)
f[i][j]=f[f[i][j-1]][j-1];
for(i=1,s=0;i<=m;i++)
{
read(u),read(v);
if(dfn[u]>dfn[v]) swap(u,v);
if(dfn[u]<dfn[v]&&las[u]>=las[v])
{
son=getson(u,v);
if(dfn[son]>1) add(dfn[v],las[v],1,dfn[son]-1);
if(las[son]<n) add(las[son]+1,n,dfn[v],las[v]);
}
else add(dfn[v],las[v],dfn[u],las[u]);
}
sort(a+1,a+s+1,cmp);
for(i=j=1;i<=n;i++)
{
while(j<=s&&a[j].x==i)
tree.add(1,1,n,a[j].yl,a[j].yr,a[j].num),j++;
ans+=i-1-tree.sum[1];
}
printf("%lld\n",ans);
return 0;
}